Submission #1096717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096717		gyg	Colors (BOI20_colors)	C++17	100 / 100	2 ms	604 KiB

Colors

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

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);
}

hset<int> vs;
bool vld(int ps) {
    return (!vs.count(ps) && 1 <= ps && ps <= n);
}
int bn_srch(int st) {
    int ps = st, drc = -1; 
    int lw = 1, hg = n;
    qry(ps), vs.insert(ps);
    while (lw != hg) {
        int md = (lw + hg) / 2;

        if (!vld(ps + drc * md)) {
            while (lw <= md && !vld(ps + drc * md)) md--;
            if (!vld(ps + drc * md)) md = (lw + hg) / 2;
        }
        if (!vld(ps + drc * md)) {
            while (!vld(ps + drc * md) || vs.count(ps)) {
                ps -= drc;
            }
            qry(ps), vs.insert(ps);
        }

        ps = ps + drc * md;
        if (qry(ps)) hg = md;
        else lw = md + 1;
        vs.insert(ps);
        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: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 24 / 24
• Subtask 5: 33 / 33