Submission #552126

#	Time	Username	Problem	Language	Result	Execution time	Memory
552126		hoanghq2004	Colors (BOI20_colors)	C++14	100 / 100	4 ms	336 KiB

Colors

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(std :: chrono :: system_clock :: now().time_since_epoch().count());

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    long long n;
    cin >> n;
    long long minv = 0;
    long long L = 1, R = n - 1;
    long long cur = 0;
    int sign = 1;
    while (L <= R) {
        long long mid = L + R >> 1;
        cur += sign * mid;
        minv = min(minv, cur);
        sign *= -1;
        L = mid + 1;
    }
    cur = 1 - minv;
    sign = 1;
    auto ask = [&](long long x) {
        cout << "? " << x << endl;
        int ans;
        cin >> ans;
        return ans;
    };
    ask(cur);
    L = 1, R = n - 1;
    long long ans = n;
    while (L <= R) {
        long long mid = L + R >> 1;
        cur += sign * mid;
        sign *= -1;
        if (ask(cur)) R = mid - 1, ans = min(ans, mid);
        else L = mid + 1;
    }
    cout << "= " << ans << endl;
}

Compilation message (stderr)

Colors.cpp: In function 'int main()':
Colors.cpp:24:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |         long long mid = L + R >> 1;
      |                         ~~^~~
Colors.cpp:42:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         long long mid = L + R >> 1;
      |                         ~~^~~

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