Submission #1204582

#TimeUsernameProblemLanguageResultExecution timeMemory
1204582UnforgettableplColors (BOI20_colors)C++20
0 / 100
1 ms440 KiB
#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<bool> tested(N+1);
    auto optTest = [&](int x)->bool{
        if(tested[x]){
            cerr<<"CALLED DOUBLE QUERY!!!\n";
            return 1;
        }
        tested[x]=true;
        cout << "? " << x << endl;
        int c;cin>>c;
        return c==1;
    };
    int offset=0;
    auto getAtPos = [&](int idx){
        if(offset)idx=N-idx+1ll;
        int center = N/2ll;
        if(N&1ll)center++;
        int dist = abs(center-idx);
        if(idx<=center)return 1ll+2ll*dist;
        else return 2ll*dist;
    };
    auto getWhichPos = [&](int x){
        int center = N/2ll;
        if(N&1ll)center++;
        int dist = x/2ll;
        if(x&1)return center-dist;
        else return center+dist;
    };
    if(N<=60){ // bruteforce
        optTest(getWhichPos(1));
        for(int i=2;i<=60;i++){
            if(optTest(getWhichPos(i))){
                cout << "= " << i-1 << endl;
                return 0;
            }
        }
        cout << "= " << N << endl;
        return 0;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...