Submission #1038328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038328		vjudge1	Colors (BOI20_colors)	C++17	100 / 100	1 ms	604 KiB

Colors

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    
    long long int N;
    cin>>N;
    long long int inf = 1, sup = N;
    queue<long long int> Q;
    long long int M = N-1;
    int alfa=0;
    long long int beta=1;
    
    while(M>0){
        Q.push((M+1)/2);
        if(alfa%2==1) beta+=(M+1)/2;
        M/=2;
        alfa++;
    }
    
    map<long long int, int> m;
    long long int dif=0;
    cout<<"? "<<beta<<endl;
    m[beta]++;
    bool b;
    alfa=0;
    cout.flush();
    cin>>b;
    while(!Q.empty()){
        dif+=Q.front();
        if(alfa%2==0){
            beta+=dif;
        }else{
            beta-=dif;
        }
        if((beta<0)|(beta>N)|(m[beta]>0)) break;
        cout<<"? "<<beta<<endl;
        m[beta]++;
        cout.flush();
        cin>>b;
        if(b){
            sup=dif;
            dif-=Q.front();
        }else{
            inf=dif+1;
        }
        Q.pop();
        alfa++;
    }
    cout<<"= "<<inf<<endl;
    return 0;
}

Compilation message (stderr)

Colors.cpp: In function 'int main()':
Colors.cpp:11:28: warning: variable 'sup' set but not used [-Wunused-but-set-variable]
   11 |     long long int inf = 1, sup = N;
      |                            ^~~

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