Submission #254780

#	Time	Username	Problem	Language	Result	Execution time	Memory
254780		model_code	Colors (BOI20_colors)	C++11	100 / 100	3 ms	328 KiB

Colors

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll find_starting_point(ll size)
{
    vector<ll> jumps;
    ll L = 1;
    while (L < size)
    {
        ll mid = L + (size - L + 1) / 2 - 1;
        jumps.push_back(mid);
        L = mid + 1;
    }

    ll epos = size;
    int dir = -1;
    reverse(jumps.begin(), jumps.end());
    for (auto t : jumps)
    {
        epos = epos + dir * t;
        dir = dir * -1;
    }

    if (dir == 1)
        return epos;
    return size - epos + 1;
}


ll solve_log(ll N, function<bool(ll)> query)
{
    // Jump from Y + X to Y
    // If 1
    //  Do solution X starting from y
    // If 0
    //  Do solution (N - X) starting from y and expanding each query by Y

    ll size = N;
    ll pos = find_starting_point(N);
    query(pos);
    ll add = 0;
    ll dir = 1;

    while (size > 1)
    {
        ll jump_sz = size / 2;
        ll inc_jump_sz = jump_sz + add;

        pos = pos + inc_jump_sz * dir;
        bool answ = query(pos);

        if (answ)
        {
            size = jump_sz;
        }
        else
        {
            size = size - jump_sz;
            add += jump_sz;
        }

        dir = dir * -1;
    }

    return add + 1;
}

bool query(ll pos)
{
    int inp;
    cout << "? " << pos << endl;
    cin >> inp;
    return inp == 1;
}

bool answer(ll pos)
{
    cout << "= " << pos << endl;
    exit(0);
}

int main()
{
    ll N;
    cin >> N;

    answer(solve_log(N, query));
}

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