BOI '20 - Colors

#include <iostream>

using namespace std;

bool query(long long p) {
    cout << "? " << p << endl;
    bool b; cin >> b;
    return b;
}

int main() {
    int tests; cin >> tests;
    while (tests--) {
        long long n; cin >> n;

        long long delta = 0;
        // simulate binary search where answer is n
        long long left = 0, right = n;
        for (int sign = 1; left+1 < right; sign = -sign) {
            long long mid = (left + right) / 2;
            delta += sign * mid;
            left = mid;
        }

        // start at k: k + delta = 1 (k = 1-delta) or k + delta = n (k = n-delta)
        long long k = -delta;
        if (k < 0) k += n;
        else k += 1;

        // perform binary search
        query(k);
        left = 0, right = n;
        for (int sign = 1; left+1 < right; sign = -sign) {
            long long mid = (left + right) / 2;
            k += sign * mid;
            if (query(k)) right = mid;
            else left = mid;
        }
        cout << "= " << right << endl;
    }
    return 0;
}