Submission #59669797

---

Source Code Expand

#include <bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using namespace atcoder;
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef pair<ll,ll> P;
constexpr ll mod=998244353;
typedef modint1000000007 mi;

ll fib[20];

int query(int q,int n){
    if(1<=q&&q<=n){
        cout<<"? "<<q<<endl;
        int a;
        cin>>a;
        return a;
    }
    else return -1;
}

void solve(){
    int n;cin>>n;
    int m=0;
    for(;fib[m]<=n;m++);
    int L=0,R=fib[m];
    int idx1=fib[m-2],idx2=fib[m-1];
    int a1=query(idx1,n);
    int a2=query(idx2,n);
    while(R-idx2>1||idx2-idx1>1||idx1-L>1){
        if(a1<a2){
            L=idx1;
            idx1=idx2;
            a1=a2;
            idx2=R-(idx1-L);
            a2=query(idx2,n);
        }
        else{
            R=idx2;
            idx2=idx1;
            a2=a1;
            idx1=L+R-idx2;
            a1=query(idx1,n);
        }
        //cout<<L<<" "<<idx1<<" "<<idx2<<" "<<R<<endl;
    }
    cout<<"! "<<max(a1,a2)<<endl;

}

int main(){
    int t;cin>>t;
    fib[1]=1;
    for(int i=2;i<20;i++)fib[i]=fib[i-1]+fib[i-2];
    rep(T,t){
        solve();
    }
}

Submission Info

Judge Result