Submission #1030729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030729		ttamx	Colors (BOI20_colors)	C++17	0 / 100	1 ms	344 KiB

Colors

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int LG=59;
const ll LIM=1e18;
const bool AUTO=true;

ll n;
ll c;
ll pre=-1;
set<ll> used;

const ll SEED=time(nullptr);

mt19937_64 rng(SEED);

ll rnd(ll x){
    return rng()%x+1;
}

inline int ask(ll x){
    if(x<1||n<x){
        cerr << x << " is out of bound";
        assert(false);
    }
    if(AUTO){
        if(used.count(x)){
            cerr << x << " has been used";
            assert(false);
        }
        used.emplace(x);
        if(pre==-1){
            pre=x;
            return 0;
        }else{
            ll d=abs(pre-x);
            pre=x;
            return d>=c;
        }
    }
    cout << "? " << x << endl;
    int res;
    cin >> res;
    return res;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    do{
        if(AUTO){
            n=rnd(LIM);
            c=rnd(n);
            pre=-1;
            used.clear();
            cerr << "n = " << n << ", " << "c = " << c << "\n";
        }else{
            cin >> n;
        }
        ll pos=1,dir=1,st=1,step=0;
        int cnt=0;
        for(ll i=n;i>1;i=(i+1)/2){
            step+=i/2;
            pos+=dir*step;
            if(pos<1){
                ll dif=1-pos;
                pos+=dif,st+=dif;
            }
            dir=-dir;
        }
        ll ans=1;
        ask(st);
        dir=1,step=0;
        for(ll i=n;i>1;){
            st+=dir*(step+i/2);
            if(!ask(st)){
                ans+=i/2;
                step+=i/2;
                i=(i+1)/2;
            }else{
                i=i/2;
            }
            dir=-dir;
        }
        cout << "= " << ans << endl;
        if(AUTO&&ans!=c){
            cerr << "expected " << c << " found " << ans << endl;
            assert(false);
        }
    }while(AUTO);
}

Compilation message (stderr)

Colors.cpp: In function 'int main()':
Colors.cpp:63:13: warning: unused variable 'cnt' [-Wunused-variable]
   63 |         int cnt=0;
      |             ^~~

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