Submission #567465

#	Time	Username	Problem	Language	Result	Execution time	Memory
567465		tengiz05	Colors (BOI20_colors)	C++17	100 / 100	4 ms	332 KiB

Colors

#include <bits/stdc++.h>
using i64 = long long;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    i64 n;
    std::cin >> n;
    i64 l = 0, r = n;
    std::vector<i64> a;
    while (l + 1 < r) {
        l = (l + r) / 2;
        a.push_back(l);
    }
    std::reverse(a.begin(), a.end());
    i64 dir = 1, pos = 0;
    for (auto x : a) {
        pos += x * dir;
        dir = -dir;
    }
    auto ask = [&](i64 x) {
        std::cout << "? " << x + 1 << std::endl;
        int f;
        std::cin >> f;
        return f;
    };
    ask(pos);
    l = 0, r = n;
    while (l + 1 < r) {
        i64 mid = (l + r) / 2;
        i64 p = pos + dir * mid;
        if (ask(p)) {
            r = mid;
        } else {
            l = mid;
        }
        dir = -dir;
        pos = p;
    }
    std::cout << "= " << r << std::endl;
    return 0;
}

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