Submission #973916

#	Time	Username	Problem	Language	Result	Execution time	Memory
973916		kl0989e	Colors (BOI20_colors)	C++17	100 / 100	3 ms	612 KiB

Colors

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define all(x) (x).begin(),(x).end()

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin >> n;
    ll s=0,c=0,l=1,r=n-1;
    for (int i=0; l<=r; i++) {
        ll m=(r-l+1>2)?((l+r)/2):r;
        if (i&1) {
            c-=m;
        }
        else {
            c+=m;
        }
        s=min(s,c);
        l=m+1;
    }
    s=-s+1;
    l=1,r=n-1;
    ll ans=n;
    if (n>1) {
        cout << "? " << s << endl;
        int a;
        cin >> a;
    }
    for (int i = 0; l<=r; i++) {
        ll m=(r-l+1>2)?((l+r)/2):r;
        if (i&1) {
            s-=m;
        }
        else {
            s+=m;
        }
        cout << "? " << s << endl;
        int resp;
        cin >> resp;
        if (resp) {
            ans=m;
            r=m-1;
        }
        else {
            l=m+1;
        }
    }
    cout << "= " << ans << endl;
    return 0;
}

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