Submission #827754

#	Time	Username	Problem	Language	Result	Execution time	Memory
827754		QwertyPi	Colors (BOI20_colors)	C++14	0 / 100	1 ms	208 KiB

Colors

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

using namespace std;

#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

const int INF = 1LL << 60;
int prv = -INF, N, C;
int hist_min, hist_max;
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

void solve(int N){
	int lo = 1, hi = N;
	while(lo != hi){
		int mid = (lo + hi) / 2;
		qry(1);
		if(qry(mid + 1)){
			hi = mid;
		}else{
			lo = mid + 1;
		}
	}
	answer(lo);
}

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

	const int MX = 100;
	for(int t = 0; t < 10000; t++){
		hist_min = INF, hist_max = -INF;
		N = rng() % MX + 1;
		C = rng() % N + 1;
		solve(N);
		printf("%lld => (%lld %lld)\n", N, hist_min, hist_max);
		shift[N] = max(shift[N], 1 - hist_min);
	}

	for(int i = 1; i <= MX; i++) printf("%lld => %lld\n", i, shift[i]);
#else
	int N; cin >> N;
	solve(N);
#endif
}

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