Submission #649843

# Submission time Handle Problem Language Result Execution time Memory
649843 2022-10-11T12:01:11 Z DJeniUp Colors (BOI20_colors) C++17
0 / 100
1 ms 208 KB
#include "bits/stdc++.h"
//#pragma GCC optimize("O3")
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef long double ld;
 
#define fr first
#define sc second
#define pb push_back
#define INF 100000000007
#define endl '\n'
#define MOD 998244353
#define A 31
#define N 500007
 
ll n;
 
int main(){
    
    cin>>n;
    ll x=0;
    ll a=n/2+1;
    ll b=a;
    ll y=0;
    ll l1=a;
    ll r1=b;
    ll l=1;
    ll r=n;
    ll f=1;
    for(int i=pow(2,20);i>=4;i/=2){
        if(x+i<n-2){
            l1=a-1;
            r1=b;
            a=max(1ll,(n-x-i+1)/2);
            b=a+x+i;
            cout<<"? "<<a<<endl;
            cout.flush();
            cin>>y;
            cout<<"? "<<b<<endl;
            cout.flush();
            cin>>y;
            if(y==0){
                x+=i;
            }
            else{
                l=a+1;
                r=b-1;
            }
        }
    }
    //if(y==1)
    if(a<l && b>r){
        while((a<l1 && f==1) || (b>r1 && f==0)){
            if(f==1){
                f=0;
                a++;
                cout<<"? "<<a<<endl;
                cout.flush();
                cin>>y;
                if(y==0){
                    cout<<"= "<<b-a+1<<endl;
                    cout.flush();
                    return 0;
                }
            }else{
                f=1;
                b--;
                cout<<"? "<<b<<endl;
                cout.flush();
                cin>>y;
                if(y==0){
                    cout<<"= "<<b-a+1<<endl;
                    cout.flush();
                    return 0;
                }
            }
        }
        cout<<"= "<<x+1<<endl;
        cout.flush();
        return 0;
    }
    
    while((a>l && f==1) || (b<r && f==0)){
        if(f==1){
            f=0;
            a--;
            cout<<"? "<<a<<endl;
            cout.flush();
            cin>>y;
            if(y==0)x++;
        }else{
            f=1;
            b++;
            cout<<"? "<<b<<endl;
            cout.flush();
            cin>>y;
            if(y==0)x++;
        }
    }
    
    cout<<"= "<<x+1<<endl;
    cout.flush();
    
    
    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB OK (3 queries)
2 Correct 0 ms 208 KB OK (10 queries)
3 Correct 1 ms 208 KB OK (5 queries)
4 Correct 1 ms 208 KB OK (6 queries)
5 Correct 1 ms 208 KB OK (7 queries)
6 Incorrect 1 ms 208 KB Wrong guess
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB OK (3 queries)
2 Correct 0 ms 208 KB OK (10 queries)
3 Correct 1 ms 208 KB OK (5 queries)
4 Correct 1 ms 208 KB OK (6 queries)
5 Correct 1 ms 208 KB OK (7 queries)
6 Incorrect 1 ms 208 KB Wrong guess
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB OK (3 queries)
2 Correct 0 ms 208 KB OK (10 queries)
3 Correct 1 ms 208 KB OK (5 queries)
4 Correct 1 ms 208 KB OK (6 queries)
5 Correct 1 ms 208 KB OK (7 queries)
6 Incorrect 1 ms 208 KB Wrong guess
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB OK (3 queries)
2 Correct 0 ms 208 KB OK (10 queries)
3 Correct 1 ms 208 KB OK (5 queries)
4 Correct 1 ms 208 KB OK (6 queries)
5 Correct 1 ms 208 KB OK (7 queries)
6 Incorrect 1 ms 208 KB Wrong guess
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB OK (3 queries)
2 Correct 0 ms 208 KB OK (10 queries)
3 Correct 1 ms 208 KB OK (5 queries)
4 Correct 1 ms 208 KB OK (6 queries)
5 Correct 1 ms 208 KB OK (7 queries)
6 Incorrect 1 ms 208 KB Wrong guess
7 Halted 0 ms 0 KB -