Submission #1126052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126052		Tob	Colors (BOI20_colors)	C++20	0 / 100	0 ms	432 KiB

Colors

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

int ask(ll x) {
	cout << "? " << x << endl;
	int o; cin >> o;
	return o;
}

int main () {
	FIO;
	ll n; cin >> n;
	ll cur = 0, of = 0;
	for (ll i = 1, o = 0; i < n; o ^= 1) {
		ll m = (n+i)/2;
		cur += (-1+2*(!o))*m;
		i = m+1;
		of = max(of, -cur);
	}
	of++;
	ask(of);
	ll lo = 1, hi = n;
	int o = 0, o1 = 0;
	while (lo < hi) {
		ll mid = (lo + hi) / 2;
		of = of+(-1+2*(!o))*mid;
		o ^= 1;
		int oo = ask(of);
		if (oo) hi = mid;
		else lo = mid+1;
		if (!o1 && oo) {
			o1 = 1;
			ask(mid);
			o = 1; of = mid;
		}
	}
	cout << "= " << lo << endl;

	return 0;
}

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