Submission #1017906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017906		Gray	Colors (BOI20_colors)	C++17	100 / 100	1 ms	656 KiB

Colors

#include <cassert>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#define ll long long
#define ln "\n"
#define ff first
#define ss second
#define ull unsigned ll
#define ld long double
const ll INF = 1e9;
const ll MOD = 1e9+7;
using namespace std;

void solve(){
	ll n; cin >> n;
	map<ll, bool> usd;
	ll l=0, r=n;
	vector<ll> moves;
	while (l+1<r) moves.push_back((r+l)/2), l=(r+l)/2;
	ll sp=1;
	for (ll i=moves.size()-1; i>=0; i--){
		if (sp+moves[i]<=n) sp+=moves[i];
		else sp-=moves[i];
	}
	usd[sp]=1;
	cout << "? " << sp << endl; ll _; cin >> _;
	l=0, r=n; ll lp=sp;
	while (l+1<r){
		ll mid = (l+r)/2;
		if (lp+mid<=n and !usd[lp+mid]){
			lp=lp+mid;
			cout << "? " << lp << endl;
		}else{
			lp=lp-mid;
			cout << "? " << lp << endl;
		}
		usd[lp]=1;
		ll x; cin >> x;
		if (x) r=mid;
		else l=mid;
	}
	cout << "= " << r << endl;
}
// 123456789
// #.####.#.
void setIO(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
}
int main(){
	setIO();
	ll t=1;
	// cin >> t;
	while (t--) solve();
}

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