Submission #1204596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204596		Unforgettablepl	Colors (BOI20_colors)	C++20	9 / 100	0 ms	432 KiB

Colors

#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 getWhichPos = [&](int x){
        int center = N/2ll;
        if(N&1ll)center++;
        int dist = x/2ll;
        int ans = -1;
        if(x&1)ans = center-dist;
        else ans = center+dist;
        if(offset)return N-ans+1;
        return ans;
    };
    if(N<=64){ // bruteforce
        optTest(getWhichPos(1));
        for(int i=2;i<=N;i++){
            if(optTest(getWhichPos(i))){
                cout << "= " << i-1 << endl;
                return 0;
            }
        }
        cout << "= " << N << endl;
        return 0;
    }
    int curr = 1;
    optTest(getWhichPos(curr));
    bool lastInward = false;
    auto test = [&](int x){
        assert(curr!=x);
        if(curr>x){ // inward spiral
            lastInward=true;
            optTest(getWhichPos(x-1));
            bool ans = optTest(getWhichPos(x));
            curr = x;
            if(!ans){
                return false;
            } else {
                int lastCurrPos = getWhichPos(curr);
                offset^=1;
                curr--;
                assert(getWhichPos(curr)==lastCurrPos);
                return true;
            }
        } else { // outward spiral
            lastInward=false;
            optTest(getWhichPos(x));
            bool ans = optTest(getWhichPos(x-1));
            curr = x-1;
            if(ans){
                return true;                
            } else {
                int lastCurrPos = getWhichPos(curr);
                offset^=1;
                curr++;
                assert(getWhichPos(curr)==lastCurrPos);
                return false;
            }
        }
    };
    int ans = 0;
    if(N&1)ans++;
    for(int jump=(1ll<<60);jump>2;jump/=2){
        if(ans+jump>N)continue;
        if(!test(ans+jump))ans+=jump;
    }
    // emulate last 2 jumps answer
    if(lastInward){
        for(int i=ans+3;i>=ans+1;i--){
            if(!optTest(getWhichPos(i))){
                cout << "= " << i << endl;
                return 0;
            }
        }
        cout << "= " << ans << endl;
        return 0;
    } else {
        for(int i=ans+1;i<=min(ans+3,N);i++){
            if(optTest(getWhichPos(i))){
                cout << "= " << i-1 << endl;
                return 0;
            }
        }
        cout << "= " << min(ans+3,N) << endl;
        return 0;
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 24
• Subtask 5: 0 / 33