Codeforces #648 Div2 G. Secure Password

本番中に気付くのは結構しんどい。
http://codeforces.com/contest/1365/problem/G

問題

パスワードPは、N要素の数列Aから作られるN要素の数列である。
P[i]は、A[i]を除くAの各要素のbitwise orで構成される。

A[i]のうちいくつかの要素を指定すると、そのbitwise orが得られるクエリがある。
このクエリを最大13回使用し、Pを特定せよ。

解法

2*log(N)のパターンは容易である。
要素番号iに関し、iのj bit目が0であるものの集合と、1であるものの集合それぞれについてクエリを行おう。
P[i]は、iが該当しない集合に対するクエリの結果のorを取ればよい。

この考えを推し進めると、いくつかの要素番号の集合を作り、それらのいくつかの和集合を作ると、1要素だけ除いた状態を作れるようにすればよい。
Editorialによると、Comb(13,6)=1716＜2^13なので、各要素番号が含まれる箇所を13か所からユニークに6か所選ぶようにすると、1000要素以上ユニークな取り方ができる。

int N;
ll A[1010];
ll R[15];
vector<int> W[1024];
vector<int> masks;

ll ask(vector<int> V) {
	if(V.empty()) return 0;
	cout<<"? "<<V.size();
	sort(ALL(V));
	FORR(v,V) cout<<" "<<(v+1);
	cout<<endl;
	ll A;
	cin>>A;
	return A;
}

void ans() {
	int i;
	cout<<"!";
	FOR(i,N) cout<<" "<<A[i];
	cout<<endl;
	exit(0);
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int mask;
	FOR(mask,1<<13) if(__builtin_popcount(mask)==6 && masks.size()<N) {
		masks.push_back(mask);
		FOR(i,13) if((mask&(1<<i))==0) W[i].push_back(masks.size()-1);
	}
	
	FOR(i,13) R[i]=ask(W[i]);
	FOR(i,N) {
		FOR(j,13) if(masks[i]&(1<<j)) A[i]|=R[j];
	}
	ans();
}

まとめ

これは思いつかなかった。