Submission #1028647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028647		DorostWef	The Big Prize (IOI17_prize)	C++17	20 / 100	31 ms	596 KiB

prize

#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 wef = cl + cr;
	int mid = (l + r) >> 1;
	int mn = mid, mx = mid;
	for (int i = 0; i < cnt - wef; 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 < min (n, 473); 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: 20 / 20
• Subtask 2: 0 / 80