なぜ本番コードが通らなかったのか…。
https://codeforces.com/contest/1081/problem/F
問題
N bitのbitmapを当てるinteractive問題である。
初期状態でT個のbitが立っている。
以下のクエリを10000回まで用い、元のbitmapを当てよ。
- 区間[L,R]を指定すると、[1,R]か[L,N]のいずれかの範囲の0/1が反転する。そして反転後の立っているbit数が返る。
- なお、反転の影響はその後のクエリに残る。
解法
(L-1) bit目まで確定しているとき、L bit目を確定させよう。
[(L+1),N]を偶数回実行すると、[(L+1),N]は必ず元に戻る。
よって20回ぐらい実行すると、[1,L]における立っているbit数が、初期状態およびそこから反転した状態の2通り発生することが期待できる。
1~(L-1)bitの値が確定しているので、この情報からL bit目を確定できる。
int N,T; int ask(int L,int R) { int x; cout<<"? "<<L<<" "<<R<<endl; cout.flush(); cin>>x; return x; } int A[303]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>T; int did=0; for(i=1;i<N;i++) { x=-1; FOR(j,15) { y=ask(i+1,N); y=ask(i+1,N); if(y!=T) { x=y; break; } } if(x==-1) { if(did+1==i/2) A[i]=1, did++; } else { if(x==(i-(did+1))+(T-(did+1))) A[i]=1, did++; } while(y!=T) { y=ask(i+1,N); y=ask(i+1,N); } } if(did<T) A[N]=1, did++; cout<<"! "; FOR(i,N) cout<<A[i+1]; cout<<endl; }
まとめ
まぁ通ってもTシャツ圏外だけどさぁ…。