Submission #804727

#	Time	Username	Problem	Language	Result	Execution time	Memory
804727		pawned	Colors (BOI20_colors)	C++17	100 / 100	6 ms	336 KiB

Colors

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;

ll comp(ll N) {
	ll low = 1;
	ll high = N - 1;
	ll curr = 0;
	ll dir = 1;	// 1 means next is going up, -1 means down
	vi all;
	all.pb(0);
	// found that C = N always gives the extreme case
	while (low <= high) {	// false, false, false, true, true, true
		ll mid = (low + high) / 2;
		curr += mid * dir;
		dir = -dir;
		all.pb(curr);
		if (mid >= N)
			high = mid - 1;
		else
			low = mid + 1;
	}
	ll currmin = 2e18;
	ll currmax = -2e18;
	for (ll i : all) {
		currmin = min(currmin, i);
		currmax = max(currmax, i);
	}
	return (-currmin + 1);	// starting point
}

ll query(ll x) {
	cout<<"? "<<x<<endl;
	cout.flush();
	ll val;
	cin>>val;
	return val;
}

int main() {
	ll N;
	cin>>N;
	ll base = comp(N);	// start here so we never go outside [1, N]
// solve
	ll low = 1;
	ll high = N - 1;
	ll ans = N;	// value of C
	ll curr = base;
	query(curr);
	ll dir = 1;	// 1 means next is going up, -1 means down
	vi all;
	all.pb(0);
	while (low <= high) {	// false, false, false, true, true, true
		ll mid = (low + high) / 2;
		curr += mid * dir;
		dir = -dir;
		all.pb(curr);
		if (query(curr)) {
			high = mid - 1;
			ans = mid;
		}
		else {
			low = mid + 1;
		}
	}
	cout<<"= "<<ans<<endl;
}

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