oj.uz

Submission #769241

# Submission time Handle Problem Language Result Execution time Memory
769241 2023-06-29T10:28:42 Z adrilen Colors (BOI20_colors) C++17
0 / 100
 0 ms 208 KB 
//#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 208 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 208 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 208 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 208 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 208 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -