Submission #1096693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096693		gyg	Colors (BOI20_colors)	C++17	9 / 100	1 ms	596 KiB

Colors

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define db long double

int n;

bool qry(int x) {
    cout << "? " << x << endl;
    bool ans; cin >> ans;
    return ans;
}
void brt() {
    int ps = 1, drc = +1, dst = n - 1; qry(ps);
    while (true) {
        int nw_ps = ps + drc * dst;
        if (ps == nw_ps || !qry(nw_ps)) { cout << "= " << dst + 1 << endl; return; }  
        ps = nw_ps, drc *= -1, dst--;
    }
    assert(false);
}

bool chck(int st) {
    int ps = st, drc = -1;
    int lw = 1, hg = n;
    while (lw != hg) {
        // cout << lw << " " << hg << ": " << ps << endl;
        int md = (lw + hg) / 2;
        ps += drc * md;
        if (ps < 1 || n < ps) return false;
        lw = md + 1;
        drc *= -1;
    }
    return true;
}
int gt_st() {
    int st = roundl(n * (db) 2 / 3);
    for (int i = st - 100; i <= st + 100; i++)
        if (chck(i)) return i;
    assert(false);
}

int bn_srch(int st) {
    int ps = st, drc = -1;
    int lw = 1, hg = n;
    qry(ps);
    while (lw != hg) {
        int md = (lw + hg) / 2;
        ps += drc * md;
        assert(1 <= ps && ps <= n);
        if (qry(ps)) hg = md;
        else lw = md + 1;
        drc *= -1;
    }
    return lw;
}

signed main() {
    cin >> n;

    if (n <= 64) { brt(); exit(0); } 

    int st = gt_st();
    int ans = bn_srch(st);
    cout << "= " << ans << endl;
}

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