Submission #1306603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306603		pvpro	Colors (BOI20_colors)	C++20	100 / 100	2 ms	452 KiB

Colors

#ifndef LOCAL
#pragma GCC Optimize("O3,Ofast,unroll-loops")
#pragma GCC Target("bmi,bmi2,avx,avx2")
#endif
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

#define int ll

#define f first 
#define s second 
#define mp make_pair 
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin() (x).rend()

mt19937 rnd(11);

int n, C;
int lst;

set<int> was;

int ask(int x) {
    assert(was.count(x) == 0);
    assert(x >= 0);
    assert(x < n);
    was.insert(x);
    cout << "? " << x + 1 << endl;
    int ans;
    #ifdef LOCAL
        ans = (abs(x - lst) >= C);
        lst = x;
    #else
        cin >> ans;
    #endif
    return ans;
}

void solve() {
    was.clear();
    cin >> n;
    int x = 0;
    int left = 0, right = 0;
    {
        int now = 0, d = 1;
        int l = 0, r = n;
        auto check = [&](int len) {
            now += d * len;
            d *= -1;
            if (now > 0) {
                right = max(right, now);
            } else {
                left = max(left, -now);
            }
            return false;
        };
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (check(m)) {
                r = m;
            } else {
                l = m;
            }
        }
        assert(right + left <= n);
        x = left;
    }
    int now = x, d = 1;
    ask(now);
    int l = 0, r = n;
    auto check = [&](int len) {
        now += d * len;
        d *= -1;
        return ask(now);
    };
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (check(m)) {
            r = m;
        } else {
            l = m;
        }
    }
    cout << "= " << r << endl;
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #else
        ios::sync_with_stdio(false);
        cin.tie(0);
    #endif
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

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