Submission #409608

#	Time	Username	Problem	Language	Result	Execution time	Memory
409608		KoD	Colors (BOI20_colors)	C++17	100 / 100	3 ms	328 KiB

Colors

#include <bits/stdc++.h>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

class rep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr usize operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

template <class T> using Vec = std::vector<T>;

bool ask(const i64 pos) {
    std::cout << "? " << pos << std::endl;
    bool f;
    std::cin >> f;
    return f;
}

void main_() {
    i64 N;
    std::cin >> N;
    Vec<i64> Ls;
    i64 L = N / 2;
    while (true) {
        Ls.push_back(L);
        L = (L + N) / 2;
        if (Ls.back() == L) {
            break;
        }
    }
    std::reverse(Ls.begin(), Ls.end());
    i64 pos = 1, coeff = 1;
    for (const auto x : Ls) {
        pos += x * coeff;
        coeff *= -1;
    }
    ask(pos);
    i64 ok = N, ng = 0;
    while (ok - ng > 1) {
        const auto md = (ok + ng) / 2;
        pos += md * coeff;
        coeff *= -1;
        (ask(pos) ? ok : ng) = md;
    }
    std::cout << "= " << ok << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    // usize cases;
    // std::cin >> cases;
    // while (cases--) main_();
    main_();
    return 0;
}

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