제출 #999701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999701		Mr_Husanboy	Colors (BOI20_colors)	C++17	100 / 100	2 ms	664 KiB

Colors

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define all(a) (a).begin(), (a).end()

long long C;
set<ll> st;
ll last = -1;
int _query = 0;

int ask(ll x){
	_query++;
	cout  << "? " << x << endl;
	if(st.count(x)){
		cout << " Used before!" << endl;
		exit(0);
	}
	st.insert(x);
	int res; 
#ifdef LOCAL
	res = (last == -1 || llabs(x - last) >= C ? 1 : 0);
#else
	cin >> res;
#endif
	last = x;
	return res;
}

void out(ll x){
	cout << "= " << x << endl;
#ifdef LOCAL
	assert(x == C);
	cout << _query << " queries called!" << endl;
#endif
}

void solve(){
	st.clear();
	_query = 0;
	ll n; cin >> n;
#ifdef LOCAL
	cin >> C;
#endif
	ll l = 0, r = n;
	ll cur = 1;
	vector<ll> q;
	while(r - l > 1){
		ll m = (l + r) / 2;
		q.push_back(m);
		l = m;
	}
	reverse(all(q));
	for(auto u : q){
		if(cur + u <= n) cur += u;
		else cur -= u;
	}

	ask(cur);

	l = 0, r = n;
	while(r - l > 1){
		ll m = (l + r) / 2;
		if(st.count(cur + m) || cur + m > n){
			cur -= m;
		}else cur += m;
		if(ask(cur)){
			r = m;
		}else l = m;
	}
	out(r);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tests = 1;
#ifdef LOCAL
	cin >> tests;
#endif
	while(tests --){
		solve();
	}
}

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