oj.uz

Submission #769203

# Submission time Handle Problem Language Result Execution time Memory
769203 2023-06-29T09:51:19 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;

    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.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 -