Submission #1149221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149221		adrilen	Colors (BOI20_colors)	C++20	0 / 100	0 ms	436 KiB

Colors

//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 2>;
using arrr = array<int, 3>;

ll last, second_last;
int query(ll p)
{
    cout << "? " << p << endl;
    swap(p, second_last);
    swap(last, second_last);
    int a;
    cin >> a;
    return a;
}

void answer(ll p)
{
    cout << "= " << p << endl;
    exit(0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll n;
    cin >> n;

    ll lower = 1, upper = n;

    vector<ll> sequence{1, n};

    for (int i = 0; i < 64 - __builtin_clzll(n); i++)
    {
        sequence.emplace_back(sequence[i] + (1ll << i) * (i & 1 ? -1 : 1));

    }

    reverse(sequence.begin(), sequence.end());

    auto it = sequence.begin();

    query(*it++);

    int ans;
    while (it != sequence.end())
    {
        ans = query(*it++);

        if (ans == 0)
        {
            lower = abs(second_last - last) + 1;
            continue;
        }
        upper = abs(second_last - last);
        break;
    }

    ll mid;
    while (lower < upper)
    {
        mid = (lower + upper) >> 1;

        if (last > n / 2) ans = query(last - mid);
        else ans = query(last + mid);

        if (ans == 0) lower = abs(second_last - last) + 1;
        else upper = abs(second_last - last);
    }


    if (lower == upper)
    {
        answer(lower);
    }

    abort();
}
/*
1000000000000000000
*/

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