Submission #551834

#	Time	Username	Problem	Language	Result	Execution time	Memory
551834		oleh1421	Colors (BOI20_colors)	C++17	0 / 100	1 ms	208 KiB

Colors

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#define endl '\n'
using namespace __gnu_pbds;
typedef long double ld;
//#define int ll
using namespace std;
mt19937 rnd(time(NULL));
typedef long long ll;
map<ll,ll>ans;
ll last=-1;
ll ask(ll x){
    cout<<"? "<<x<<endl;
    ll res;cin>>res;
    if (last!=-1) ans[abs(x-last)]=res;
    last=x;
    return res;
}
void solve(){
    ll n;cin>>n;
    ll L=1,R=n/2+1;
    ask(1);
    if (ask(n)==0){
        cout<<"! "<<n<<endl;
        return;
    }


    while (R-L>3){
        ll mid=(L+R)/2ll;
        int cur=ask(mid);
        cur=ask(n-mid+1);
        if (cur) L=mid;
        else R=mid;
    }
    int l=L;
    int r=n-L+1;
    int ans=r-l;
    while (r-l>1){
        if ((l+r+n)%2){
            int cur=ask(++l);
            if (!cur) break;
        } else {
            int cur=ask(--r);
            if (!cur) break;
        }
        ans=r-l;
    }
    cout<<"= "<<ans<<endl;

}

int32_t main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt=1;
    while (tt--){
        solve();
    }

    return 0;
}

/**
1
8
6 7
2 3
8 6
5 4
1 7
3 6
4 3
**/

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