Submission #1017815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017815		Gray	Colors (BOI20_colors)	C++17	67 / 100	65 ms	116636 KiB

Colors

#include <cassert>
#include <iostream>
#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;
	vector<bool> usd(n+1);
	ll sp=n;
	ll l=0, r=n;
	vector<ll> moves;
	while (l+1<r) moves.push_back((r+l)/2), l=(r+l)/2;
	for (ll i=0; i<(ll)moves.size(); i++){
		if (i%2==0) sp-=moves[moves.size()-i-1];
		else sp+=moves[moves.size()-i-1];
	}
	usd[sp]=1;
	cout << "? " << sp << endl; ll _; cin >> _;
	l=0, r=n; ll lp=sp;
	ll dir=moves.size()%2;
	while (l+1<r){
		ll mid = (l+r)/2;
		if (dir and lp+mid<=n and !usd[lp+mid]){
			lp=lp+mid;
			dir=0;
			cout << "? " << lp << endl;
		}else{
			dir=1;
			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: 0 / 33