Submission #769241

#	Time	Username	Problem	Language	Result	Execution time	Memory
769241		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;

    if (n == 3) {
        int a, b;
        query(1);
        a = query(3);
        b = query(2);

        if (a == 0) cout << "= " << 3 << endl;
        else if (b == 0) cout << "= " << 2 << endl;
        else cout << "= " << 1 << endl;
        return 0;
    }




    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));
    }

    if (seq[seq.size() - 1] == seq[seq.size() - 2]) seq.pop_back();

    // for (ll i : seq) cout << i << " ";
    // cout << "\n";



    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;

            if (dd >= 0) {
                d -= (1ll << dd);

                while (d < 1 && l != r)
                {
                    
                    d += (1ll << dd);
                    dd--;
                    d -= (1ll << dd);   
                }
            }
        } else {
            l = d + 1;

            if (dd >= 0) {
                d += (1ll << dd);

                while (d >= n && l != r)
                {
                    d -= (1ll << dd);
                    dd--;
                    d += (1ll << dd);

                }
            }
        }
        dd--;
        add ^= 1;
    }

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

// 1000000000000000000

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