oj.uz

Submission #914258

# Submission time Handle Problem Language Result Execution time Memory
914258 2024-01-21T13:04:30 Z Abito Colors (BOI20_colors) C++14
0 / 100
 0 ms 448 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
//#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
#define ll long long
#define y1 YONE
#define free freeee
#define lcm llcm
/*
⠄⠄⠄⠄⢠⣿⣿⣿⣿⣿⢻⣿⣿⣿⣿⣿⣿⣿⣿⣯⢻⣿⣿⣿⣿⣆⠄⠄⠄
⠄⠄⣼⢀⣿⣿⣿⣿⣏⡏⠄⠹⣿⣿⣿⣿⣿⣿⣿⣿⣧⢻⣿⣿⣿⣿⡆⠄⠄
⠄⠄⡟⣼⣿⣿⣿⣿⣿⠄⠄⠄⠈⠻⣿⣿⣿⣿⣿⣿⣿⣇⢻⣿⣿⣿⣿⠄⠄
⠄⢰⠃⣿⣿⠿⣿⣿⣿⠄⠄⠄⠄⠄⠄⠙⠿⣿⣿⣿⣿⣿⠄⢿⣿⣿⣿⡄⠄
⠄⢸⢠⣿⣿⣧⡙⣿⣿⡆⠄⠄⠄⠄⠄⠄⠄⠈⠛⢿⣿⣿⡇⠸⣿⡿⣸⡇⠄
⠄⠈⡆⣿⣿⣿⣿⣦⡙⠳⠄⠄⠄⠄⠄⠄⢀⣠⣤⣀⣈⠙⠃⠄⠿⢇⣿⡇⠄
⠄⠄⡇⢿⣿⣿⣿⣿⡇⠄⠄⠄⠄⠄⣠⣶⣿⣿⣿⣿⣿⣿⣷⣆⡀⣼⣿⡇⠄
⠄⠄⢹⡘⣿⣿⣿⢿⣷⡀⠄⢀⣴⣾⣟⠉⠉⠉⠉⣽⣿⣿⣿⣿⠇⢹⣿⠃⠄
⠄⠄⠄⢷⡘⢿⣿⣎⢻⣷⠰⣿⣿⣿⣿⣦⣀⣀⣴⣿⣿⣿⠟⢫⡾⢸⡟⠄.
⠄⠄⠄⠄⠻⣦⡙⠿⣧⠙⢷⠙⠻⠿⢿⡿⠿⠿⠛⠋⠉⠄⠂⠘⠁⠞⠄⠄⠄
⠄⠄⠄⠄⠄⠈⠙⠑⣠⣤⣴⡖⠄⠿⣋⣉⣉⡁⠄⢾⣦⠄⠄⠄⠄⠄⠄⠄⠄
*/
typedef unsigned long long ull;
using namespace std;
int n,c=1;
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n;
    int last=n/2,l=1,r=n-1,mid;
    set<int> s;
    s.ep(last);
    bool h;
    cout<<"? "<<last<<endl;cin>>h;
    while (l<=r){
        mid=(l+r)/2;
        if (!s.count(last-mid) && last>mid){
            cout<<"? "<<last-mid<<endl;
            cin>>h;
            s.ep(last-mid);
            last-=mid;
        }
        elif (!s.count(last+mid) && last+mid<=n){
            cout<<"? "<<last+mid<<endl;
            cin>>h;
            s.ep(last+mid);
            last+=mid;
        }
        else{
            for (int i=max(1LL,last-100);i<=min(n,last+100);i++){
                if (s.count(i)) continue;
                if (s.count(i+mid) && s.count(i-mid)) continue;
                if (!s.count(i+mid)){
                    cout<<"? "<<i<<endl;cin>>h;
                    cout<<"? "<<i+mid<<endl;cin>>h;
                    s.ep(i);
                    s.ep(i+mid);
                    last=i+mid;
                    break;
                }
                if (!s.count(i-mid)){
                    cout<<"? "<<i<<endl;cin>>h;
                    cout<<"? "<<i-mid<<endl;cin>>h;
                    s.ep(i);
                    s.ep(i-mid);
                    last=i-mid;
                    break;
                }
            }
        }
        if (!h) l=c=mid+1;
        else r=mid-1;
    }cout<<"= "<<c<<endl;
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB OK (4 queries)
2 Runtime error 0 ms 448 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB OK (4 queries)
2 Runtime error 0 ms 448 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB OK (4 queries)
2 Runtime error 0 ms 448 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB OK (4 queries)
2 Runtime error 0 ms 448 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB OK (4 queries)
2 Runtime error 0 ms 448 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -