The hat [Codeforces Round #503 (by SIS, Div. 1) B]

http://codeforces.com/contest/1019/problem/B

インタラクティブ問題。
N要素（Nは偶数）の配列Aがある。
この配列は以下のような特徴がある。

• 隠されている
• 円状である。つまり、1番目とN番目は隣接していると考える
• 隣接している要素の数はちょうど1だけ離れている

行えるクエリは2種類
質問クエリ「? i」i番目の要素の数を聞く
回答クエリ「! i」i番目の要素が答えであると答える。このクエリ後は即座に終了する必要がある
　
60回以下の質問でi番目の数とi+N/2番目の数が等しいようなiを答えよ。
存在しないなら-1と答える。

考察過程

1. 60回以下なので二分探索系なのは確定
2. 隣接要素はちょうど1だけ離れているというのをうまく使えないか
3. 天啓「B[i] = A[i+N/2] - A[i]」を使えばいいのでは？
4. B[i]とB[i+1]の差を考えてみると0, +2, -2のどれかになっている
5. B[i]=0であれば、答えの条件を満たす
6. しかもB[i+N/2] = -B[i]となっている
7. 中間値の定理のような雰囲気を感じる
8. これを考えるとB[i], B[i+1], ... , B[i + N/2]はB[i], B[i+1], ..., -B[i]なので中間値の定理的に答えが必ず存在しそう
9. B[i]がもともと奇数なら答えが無い（これはN/2が奇数の場合は奇数となる）
10. それ以外なら答えがあるので、中間値の定理と二分探索を使って、答えを導いていく
　

解法

http://codeforces.com/contest/1019/submission/41484240

答えが無い場合はN/2が奇数の場合なので、このときは除いておこう。
N/2が偶数であれば答えは必ず存在する。

B[i] = A[i+N/2] - A[i]とする。
それに伴って、質問をするときは、いつもA[i + N/2]とA[i]を聞くことにする。
diff(i) := A[i+N/2]-A[i]を返す
　
二分探索をする。
L=0, R=N/2が初期状態である。
するとLx = B[L], Rx = B[R] = -B[L]。
二分探索をするが、LxとRxの符号が異なるように維持しながら二分探索をしていく。
LxとRxの符号が異なるようにしていれば、その間に中間値の定理より、0となる要素の存在を維持できる。
あとは、0となる要素が出てくるまで頑張る。

int N;
//---------------------------------------------------------------------------------------------------
int test = 0;
int testcase[8] = { 1,2,1,2,3,4,3,2};
int ask(int i) {
    if (test) return testcase[i];

    printf("? %d\n", i + 1);
    fflush(stdout);

    int x; cin >> x;
    return x;
}
void ans(int i) {
    printf("! %d\n", i + 1);
    fflush(stdout);
}
int diff(int i) {
    if (test) return testcase[i + N / 2] - testcase[i];

    int a = ask(i);
    int b = ask(i + N / 2);
    return b - a;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    if ((N / 2) % 2 == 1) {
        ans(-2);
        return;
    }

    int L = 0, R = N / 2;
    int Lx = diff(L);
    int Rx = -Lx;
    if (Lx == 0) {
        ans(0);
        return;
    }
    while (L + 1 != R) {
        int md = (L + R) / 2;
        int x = diff(md);

        if (x == 0) {
            ans(md);
            return;
        }

        if (Lx < 0 and x < 0) {
            Lx = x;
            L = md;
        } else if(Rx < 0 and x < 0) {
            Rx = x;
            R = md;
        }
        else if (0 < Lx and 0 < x) {
            Lx = x;
            L = md;
        }
        else if (0 < Rx and 0 < x) {
            Rx = x;
            R = md;
        }
    }
}