Submission #827770

#	Time	Username	Problem	Language	Result	Execution time	Memory
827770		QwertyPi	Colors (BOI20_colors)	C++14	100 / 100	2 ms	336 KiB

Colors

#include <bits/stdc++.h>
#define int long long

using namespace std;

int hist_min, hist_max;
const int INF = 1LL << 60;

#ifndef LOCAL
bool qry(int x){
	cout << "? " << x << endl;
	bool r; cin >> r;
	return r;
}
void answer(int x){
	cout << "= " << x << endl;
	exit(0);
}
#else

int prv = -INF, N, C;
int shift[100];

bool qry(int x){
	hist_min = min(hist_min, x);
	hist_max = max(hist_max, x);
	cout << "Q " << x << ' ' << N << endl;
	assert(1 <= x && x <= N);
	if(prv == -INF) { prv = x; return 0; } 
	bool res = abs(x - prv) >= C; prv = x;
	return res;
}
void answer(int x){
	assert(x == C);
}
#endif


bool fake_qry(int x){
	hist_min = min(hist_min, x);
	hist_max = max(hist_max, x);
	return false;
}
void fake_answer(int x){
	return;
}
void fake_solve(int N){
	int lo = 1, hi = N;
	int prv = 1; fake_qry(prv);
	bool forward = true;
	while(lo < hi){
		int mid = (lo + hi - 1) / 2;
		int nxt = forward ? prv + mid : prv - mid;
		forward ^= true;
		if(fake_qry(nxt)){
			hi = mid;
		}else{
			lo = mid + 1;
		}
		prv = nxt;
	}
	fake_answer(lo);
}

void solve(int N){
	fake_solve(N);
	int lo = 1, hi = N;
	int prv = 2 - hist_min; qry(prv);
	bool forward = true;
	while(lo != hi){
		int mid = (lo + hi - 1) / 2;
		int nxt = forward ? prv + mid : prv - mid;
		forward ^= true;
		if(qry(nxt)){
			hi = mid;
		}else{
			lo = mid + 1;
		}
		prv = nxt;
	}
	answer(lo);
}

int32_t main(){
#ifdef LOCAL
	random_device rd;
	mt19937 rng(rd());

	const int MX = 2;
	for(int t = 0; t < 1; t++){
		hist_min = INF, hist_max = -INF;
		N = rng() % MX + 1;
		C = rng() % N + 1;
		N = 2; C = 1;
		solve(N);
		shift[N] = max(shift[N], 1 - hist_min);
	}

#else
	hist_min = INF, hist_max = -INF;
	int N; cin >> N;
	solve(N);
#endif
}

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