Submission #553790

#	Time	Username	Problem	Language	Result	Execution time	Memory
553790		Arvin	Colors (BOI20_colors)	C++11	0 / 100	1 ms	208 KiB

Colors

#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;
}

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