제출 #553790

#제출 시각아이디문제언어결과실행 시간메모리
553790ArvinColors (BOI20_colors)C++11
0 / 100
1 ms208 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long

bool ask(ll n){
	cout << "? " << n << endl;
	
	bool res;
	cin >> res;
	
	return res;
}

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	
	ll n;
	cin >> n;
	
	ask(1);
	
	set<ll> st;
	st.insert(1);
	
	ll pos = 1;
	ll ans = 0;
	ll lg = log2(n);
	for(int x=lg;x>=0;x--){
		ll val = min(n-1, ans|((1 << x)-1));
		
		while((pos+val > n || st.count(pos+val)) && (pos-val <= 0 || st.count(pos-val))){
			if(pos >= n) break;
			pos++;
		}
		while((pos+val > n || st.count(pos+val)) && (pos-val <= 0 || st.count(pos-val))){
			if(pos <= 1) break;
			pos--;
		}
		if(!st.count(pos)){
			st.insert(pos);
			ask(pos);
		}
		
		if(pos+val <= n && !st.count(pos+val)){
			if(!ask(pos+val)){
				ans |= (1 << x);
			}
			pos += val;
		} else if(pos-val > 0 && !st.count(pos-val)){
			if(!ask(pos-val)){
				ans |= (1 << x);
			}
			pos -= val;
		}
		st.insert(pos);
	}
	cout << "= " << ans << endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...