Avito Cool Challenge 2018 : F. Tricky Interactor

なぜ本番コードが通らなかったのか…。
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シャツ圏外だけどさぁ…。