http://codeforces.com/contest/835/problem/E
概要
インタラクティブ問題。
N要素の未知の配列がある。
これは2要素のみYで他は全てXである。
最大19回「指定の要素のxor和を返す質問」ができる。
Yが書かれている要素番号を答えよ。
解説
http://codeforces.com/contest/835/submission/29088591
公式解説とkmjpさんの解法を見て理解した。
質問をすると4パターンの返答がありうる
1. 質問の個数が偶数で、Yの要素が偶数なら「0」
2. 質問の個数が偶数で、Yの要素が奇数なら「x xor y」
3. 質問の個数が奇数で、Yの要素が偶数なら「x」
4. 質問の個数が奇数で、Yの要素が奇数なら「y」
まず、10回質問を使って、答えのbit-wise diffを取る。
具体的には以下の手続きをする
for(i = 0...9) { vector<int> v = {i番目のビットが1である要素番号}; if(ask(v)の答えが奇数) { // 2つの答えでは、i番目のビットは異なっている } }
diff変数を用意する。
もう一つ、maxbit変数として異なっている最上位ビットを保持しておく。
次に、答えのうち小さい方を9回で特定する。
探す領域はmaxbitビット目が0であるものだけとする。
こうすることで、2つの答えのうち1つだけを対象とした探索ができる。
あとは、上記の手続きと同じような感じで答えを求めて、diffでもう一つの答えを見つけたら、それを答える。
int N, X, Y; //--------------------------------------------------------------------------------------------------- int ask(vector<int> &v) { printf("? %d", v.size()); fore(i, v) printf(" %d", i + 1); printf("\n"); fflush(stdout); int res; cin >> res; return res; } void answer(int a, int b) { printf("! %d %d\n", a + 1, b + 1); fflush(stdout); } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> X >> Y; int diff = 0; int maxbit = -1; rep(i, 0, 10) { vector<int> v; rep(j, 0, N) if (j & (1 << i)) v.push_back(j); if (v.empty()) continue; int res = ask(v); if (res == (X^Y) || res == Y) { diff |= (1 << i); maxbit = i; } } int a1 = 0; rep(i, 0, 10) if (i != maxbit) { vector<int> v; rep(j, 0, N) if (j & (1 << i)) if ((j & (1 << maxbit)) == 0) v.push_back(j); if (v.empty()) continue; int res = ask(v); if (res == (X^Y) || res == Y) a1 |= (1 << i); } answer(a1, a1 ^ diff); }