053 - Discrete Dowsing（★7）- 黄金分割探索を用いた想定解 (naoya_t) + 自作ジャッジサーバスクリプト https://gist.github.com/naoyat/d4a0778fd6aa543d23e0138582208db9

053.cc

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
#define rep(var,n)  for(int var=0;var<(n);++var)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

double phi = (1.0 + sqrt(5)) * 0.5, w = 1.0 / (1.0 + phi);
inline double calc_u(int d) { return round(d * w); }

int listen(){
    int y; scanf("%d%*c", &y); return y;
}
int ask(int x){
    printf("? %d\n", x); fflush(stdout);
    return listen();
}
void answer(int a_k){
    printf("! %d\n", a_k); fflush(stdout);
}

void solve(int N) {
    vi memo(N+1, -1);
    auto f = [&](int x) -> int {
        // assert(IN(x, 1, N));
        if (memo[x] == -1) memo[x] = ask(x);
        return memo[x];
    };
    auto sub = [&](auto sub, int lo, int p, int q, int hi) -> int {
        // 開区間 (lo, p, q, hi). p,qは黄金分割の2点(1:φ, φ:1)
        int d = hi - lo;
        // assert(d >= 2);
        if (d == 2) return lo+1;
        if (d == 3) return f(lo+1) > f(lo+2) ? lo+1 : lo+2;
        // assert(d >= 4);
        int a_p = f(p), a_q = f(q);
        if (a_p == a_q) {
            int d = q - p;
            int u = calc_u(d);
            int p2 = p + u, q2 = q - u;
            if (p2 == q2) --p2;
            return sub(sub, p, p2, q2, q);
        }
        else if (a_p < a_q) {
            int d = hi - p;
            int u = calc_u(d);
            int q0 = hi - u;
            if (q0 == q) ++q0;
            // assert(q < q0);
            return sub(sub, p, q, q0, hi);
        }
        else {
            int d = q - lo;
            int u = calc_u(d);
            int p0 = lo + u;
            if (p0 == p) --p0;
            // assert(p0 < p);
            return sub(sub, lo, p0, p, q);
        }
    };

    int u = calc_u(N+1);
    int p = 0 + u, q = (N+1) - u;
    if (p == q) --p;
    int k = sub(sub, 0, p, q, N+1);
    int a_k = f(k);
    answer(a_k);
}

int main() {
    int T = listen();
    rep(z,T){
        int N = listen();
        solve(N);
    }
    return 0;
}