제출 #1279995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279995		MisterReaper	Colors (BOI20_colors)	C++20	100 / 100	2 ms	424 KiB

Colors

// File colors.cpp created on 16.10.2025 at 16:20:19
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

i64 N;
#ifdef LOCAL
    i64 C;
    i64 lst = -1;
#endif

bool ask(i64 x) {
    assert(1 <= x && x <= N);
    bool res;
    std::cout << "? " << x << std::endl;
    #ifdef LOCAL
        if (lst == -1) {
            res = 0;
        } else {
            res = std::abs(x - lst) >= C;
        }
        lst = x;
    #else
        std::cin >> res;
    #endif
    return res;
}

i64 find_start() {
    std::vector<i64> jmp;
    i64 x = 1;
    while (x < N) {
        i64 nx = x + (N - x + 1) / 2 - 1;
        jmp.emplace_back(nx);
        x = nx + 1;
    }
    std::reverse(jmp.begin(), jmp.end());
    i64 p = N, dir = -1;
    for (auto i : jmp) {
        p += i * dir;
        dir *= -1;
    }
    if (dir == +1) {
        return p;
    } else {
        return N - p + 1;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> N;

    #ifdef LOCAL
        std::cin >> C;
    #endif

    i64 p = find_start();
    debug(p);

    ask(p);

    i64 len = N, dir = +1, ans = 0;
    while (len > 1) {
        i64 m = len / 2;
        i64 np = p + dir * (ans + m);
        debug(np);
        bool res = ask(np);
        if (res == 1) {
            len = m;
        } else {
            ans += m;
            len -= m;
        }
        dir *= -1;
        p = np;
    }

    ans += 1;

    std::cout << "= " << ans << std::endl;

    #ifdef LOCAL
        assert(ans == C);
    #endif

    return 0;
}

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