Submission #1096919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096919		gyg	Colors (BOI20_colors)	C++17	0 / 100	0 ms	344 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;
}

bool chck(int st) {
    int ps = st, drc = -1;
    int lw = 1, hg = n;
    while (lw != hg) {
        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; qry(ps);
    int add = 0, drc = -1, lw = 1, hg = n;
    while (lw != hg) {
        // cout << lw << " " << hg << ": " << ps << endl;
        int hlf = (hg - lw + 1) / 2;
        ps += drc * (hlf + add);
        if (qry(ps)) hg = lw + hlf - 1;
        else {
            add += hlf;
            lw = lw + hlf;
        }
        drc *= -1;
    }
    return lw;
}

signed main() {
    cin >> n;

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

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