제출 #804727

#제출 시각아이디문제언어결과실행 시간메모리
804727pawnedColors (BOI20_colors)C++17
100 / 100
6 ms336 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...