Codeforces #1064 : Div1 C. Binary Wine

本番はBよりあっさり解いている。
https://codeforces.com/contest/2165/problem/C

問題

整数列Aが与えられる。
クエリとして整数Cが与えられるので、以下に答えよ。

• 整数列Bを、0≦B[i]≦A[i]かかつxor(B)=Cとなるように作りたい。
• 必要に応じてAをインクリメントする場合、最少インクリメント回数を求めよ。

解法

CをMSBから順に合わせて行く。
既存のAのうち、CのMSB以上の値が無いなら、Aの最大値をCのMSBになるまでインクリメントする、を繰り返そう。

int T,N,Q;
int A[505050];
vector<int> B[31];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>Q;
		FOR(i,N) cin>>A[i];
		sort(A,A+N);
		while(Q--) {
			int C;
			cin>>C;
			ll ret=0;
			multiset<int> S;
			int cur=N-1;
			while(C&&(cur>=0||S.size())) {
				int v=-1;
				if(cur>=0&&S.size()) {
					if(A[cur]>*S.rbegin()) goto aa;
					else goto bb;
				}
				else if(cur>=0) {
					aa:
					v=A[cur];
					cur--;
				}
				else {
					bb:
					v=*S.rbegin();
					S.erase(S.find(v));
				}
				if(v==0) {
					ret+=C;
					break;
				}
				if(C<=v) {
					break;
				}
				//MSBが一緒
				x=-1,y=-1;
				FOR(j,30) {
					if(C&(1<<j)) x=j;
					if(v&(1<<j)) y=j;
				}
				if(x==y) {
					S.insert(v^(1<<y));
					C^=1<<y;
				}
				else {
					ret+=(1<<x)-v;
					C^=1<<x;
				}
			}
			cout<<ret<<endl;
			
		}
		
	}
}

まとめ

なにがWineなんだろ。