oj.uz

Submission #827754

# Submission time Handle Problem Language Result Execution time Memory
827754 2023-08-16T17:25:22 Z QwertyPi Colors (BOI20_colors) C++14
0 / 100
 1 ms 208 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Hair color 1 was used multiple times
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Hair color 1 was used multiple times
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Hair color 1 was used multiple times
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Hair color 1 was used multiple times
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Hair color 1 was used multiple times
2 Halted 0 ms 0 KB -