oj.uz

Submission #1028637

# Submission time Handle Problem Language Result Execution time Memory
1028637 2024-07-20T06:33:16 Z DorostWef The Big Prize (IOI17_prize) C++17
0 / 100
 49 ms 344 KB 
#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

int cnt;

int solve (int l, int r, int cl, int cr) {
	if (l > r || cl + cr == cnt)
		return 0;
	if (l == r) {
		vector<int> a = ask(l);
		if (a[0] + a[1] == 0)
			return l;
		return 0;
	}
	int mid = (l + r) >> 1;
	int mn = mid, mx = mid;
	for (int i = 0; i <= (r - l + 1); i++) {
		int x;
		if (i % 2 == 1) {
			x = mid + i / 2 + 1;
		} else {
			x = mid - i / 2;
		}
		mn = min (mn, x);
		mx = max (mx, x);
		vector<int> a = ask(x);
		if (a[0] + a[1] == 0)
			return x;
		if (a[0] + a[1] == cnt) {
			return solve (l, mn - 1, cl, a[1]) ^ solve (mx + 1, r, a[0], cr);
		}
	}
	return 0;
}

int find_best(int n) {
	for (int i = 0; i < n; i++) {
		vector<int> a = ask(i);
		if(a[0] + a[1] == 0)
			return i;
		cnt = max (cnt, a[0] + a[1]);
	}
	return solve (0, n - 1, 0, 0);
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -