oj.uz

Submission #551834

# Submission time Handle Problem Language Result Execution time Memory
551834 2022-04-21T17:05:44 Z oleh1421 Colors (BOI20_colors) C++17
0 / 100
 1 ms 208 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB OK (5 queries)
2 Incorrect 1 ms 208 KB Wrong guess
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB OK (5 queries)
2 Incorrect 1 ms 208 KB Wrong guess
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB OK (5 queries)
2 Incorrect 1 ms 208 KB Wrong guess
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB OK (5 queries)
2 Incorrect 1 ms 208 KB Wrong guess
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB OK (5 queries)
2 Incorrect 1 ms 208 KB Wrong guess
3 Halted 0 ms 0 KB -