Codeforces #685 Div2 E2. Bitwise Queries (Hard Version)

不参加だった回。
https://codeforces.com/contest/1451/problem/E2

問題

2の累乗である長さNの数列Aの中身を当てるinteractive問題である。
各値は[0,N-1]の範囲の整数値を取る。

以下のクエリをN+1回まで用いて、Aを求めよ。

• 異なる2つの要素を選択し、andかorかxorを取った値を返す

解法

1個要素A[i]を確定できれば、あとはA[i] xor A[j]を問うことで他の要素は1クエリで1要素埋められる。

まず、A[0] xor A[i] = B[i]を片っ端から求めよう。

• もしB[i]=B[j]となる(i,j)があれば、A[i] and A[j] = A[i]よりA[i]・A[j]を特定できる。
  • A[i] = B[i] xor A[0]より、A[0]を求め、残りも求められる。
• そのような(i,j)がない場合、B[1]～B[N-1]がすべて異なる。p xor q = (N-1)となり、かつB[i]=p、B[j]=qとなるp,q,i,jを求めよう。(A[0] and A[i]) or (A[0] and A[j]) = A[0]より、追加クエリ2回でA[0]を特定できる。

int N;
int A[1<<16];
int B[1<<16];
vector<int> cand[1<<16];

int ask(string A,int a,int b) {
	cout<<A<<" "<<(a+1)<<" "<<(b+1)<<endl;
	cin>>a;
	return a;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	
	cand[0].push_back(0);
	for(i=1;i<N;i++) {
		B[i]=ask("XOR",0,i);
		cand[B[i]].push_back(i);
	}
	FOR(i,N) {
		if(cand[i].size()>=2) {
			x=cand[i][0];
			y=cand[i][1];
			A[x]=A[y]=ask("AND",x,y);
			if(i) A[0]=B[x]^A[x];
			cout<<"! "<<A[0];
			for(i=1;i<N;i++) {
				cout<<" "<<(A[0]^B[i]);
			}
			cout<<endl;
			return;
		}
	}
	x=cand[1][0];
	y=cand[N-2][0];
	A[0]|=ask("AND",0,x);
	A[0]|=ask("AND",0,y);
	cout<<"! "<<A[0];
	for(i=1;i<N;i++) {
		cout<<" "<<(A[0]^B[i]);
	}
	cout<<endl;
	return;
	
	
}

まとめ

Div2回のEの割に正答者が多い。