Submission #769203

#	Time	Username	Problem	Language	Result	Execution time	Memory
769203		adrilen	Colors (BOI20_colors)	C++17	0 / 100	0 ms	208 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>;

set <ll> used;

int query(ll p)
{
    used.insert(p);
    cout << "? " << p << endl;
    int a;
    cin >> a;
    return a;
}


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

    vector <ll> seq = { n };

    for (ll i = 0; seq.size() == 1 || abs(seq[i - 1] - seq[i]) >= n / 2; i++)
    {
        seq.emplace_back(seq.back() + (n - (1ll << i)) * (i & 1 ? 1 : -1));
    }


    ll dd = 62 - __builtin_clzll(n);

    ll a, b, d;
    a = seq.back(), b = seq[seq.size() - 2];
    d = abs(a - b);
    bool add = (a < b);

    ll l = 1, r = n;

    query(a);
    int ans;
    while (l != r)
    {
        a += (add ? d : -d);
        ans = query(a);

        if (ans)
        {
            r = d;
            d -= (1ll << dd--);
        } else {
            l = d + 1;
            d += (1ll << dd--);
        }

        add ^= 1;
    }

    cout << l << "\n";
    // cerr << used.size() << "\n";
    
}

// 1,000,000,000,000,000

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