Submission #914249

#	Time	Username	Problem	Language	Result	Execution time	Memory
914249		Abito	Colors (BOI20_colors)	C++14	9 / 100	3055 ms	500 KiB

Colors

#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);
    mt19937 rnd(time(0));
    cin>>n;
    set<int> s;
    for (int i=1;i<=n;i++) s.ep(i);
    bool h;
    if (n<=64){
        cout<<"? 1"<<endl;cin>>h;
        for (int i=2;i<=n;i++) s.ep(i);
        int x=n-1,last=1;
        for (int i=1;i<n;i++){
            if (s.count(last+x)) cout<<"? "<<last+x<<endl,s.erase(last+x),last+=x;
            else cout<<"? "<<last-x<<endl,s.erase(last-x),last-=x;
            cin>>h;
            if (!h) {c=x+1;break;}
            else x--;
        }cout<<"= "<<c<<endl;
        return 0;
    }
    int l=1,r=n-1,mid;
    while (l<=r){
        mid=(l+r)/2;
        while (true){
            int x=rnd()%n+1;
            if (!s.count(x) || !s.count(mid+x)) continue;
            cout<<"? "<<x<<endl;cin>>h;
            cout<<"? "<<mid+x<<endl;cin>>h;
            s.erase(x);
            s.erase(mid+x);
            break;
        }
        if (!h){
            c=mid+1;
            l=mid+1;
        }else r=mid-1;
    }cout<<"= "<<c<<endl;
    return 0;
}

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