Submission #254862

#	Time	Username	Problem	Language	Result	Execution time	Memory
254862		dolphingarlic	Colors (BOI20_colors)	C++14	100 / 100	2 ms	504 KiB

Colors

/*
Baltic 2020 Colors
- Binary search + randomisation to avoid collisions
- Complexity: log(N) + 1 queries
*/

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

map<ll, bool> used;

bool ask(ll i) {
    used[i] = 1;
    cout << "? " << i << endl;
    bool x;
    cin >> x;
    return x;
}

int main() {
    srand(69420);
    ll n;
    cin >> n;
    ll l = 1, r = n;
    vector<ll> im;
    ll l1 = l, r1 = r;
    while (l1 < r1) {
        ll mid = (l1 + r1) / 2;
        im.push_back(mid);
        l1 = mid + 1;
    }
    reverse(im.begin(), im.end());
    ll curr = 1;
    FOR(i, 0, im.size()) {
        if (i & 1) curr -= im[i];
        else curr += im[i];
    }
    ask(curr);
    while (l != r) {
        ll mid = (l + r) / 2;
        if (curr + mid <= n && !used[curr + mid]) {
            curr += mid;
            if (!ask(curr)) l = mid + 1;
            else r = mid;
        } else if (curr - mid >= 1 && !used[curr - mid]) {
            curr -= mid;
            if (!ask(curr)) l = mid + 1;
            else r = mid;
        } else {
            l1 = l, r1 = r;
            im.clear();
            while (l1 < r1) {
                ll mid = (l1 + r1) / 2;
                im.push_back(mid);
                l1 = mid + 1;
            }
            reverse(im.begin(), im.end());
            curr = 1;
            FOR(i, 0, im.size()) {
                if (i & 1) curr -= im[i];
                else curr += im[i];
            }
            if (curr >= r + 1 - curr) curr = r + 1 - curr;
            curr = rand() % curr + 1;
            while (used[curr] || used[curr + mid] || used[curr - mid]) ++curr;
            ask(curr);
        }
    }
    cout << "= " << l << endl;
    return 0;
}

Compilation message (stderr)

Colors.cpp: In function 'int main()':
Colors.cpp:8:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
Colors.cpp:36:9:
     FOR(i, 0, im.size()) {
         ~~~~~~~~~~~~~~~                 
Colors.cpp:36:5: note: in expansion of macro 'FOR'
     FOR(i, 0, im.size()) {
     ^~~
Colors.cpp:8:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
Colors.cpp:61:17:
             FOR(i, 0, im.size()) {
                 ~~~~~~~~~~~~~~~         
Colors.cpp:61:13: note: in expansion of macro 'FOR'
             FOR(i, 0, im.size()) {
             ^~~

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