Submission #1069294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069294		MinaRagy06	The Big Prize (IOI17_prize)	C++17	90 / 100	66 ms	6292 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()

const int N = 200'005;
vector<int> asked[N];
int cnt;
vector<int> get(int i) {
	if (SZ(asked[i])) {
		return asked[i];
	}
	cnt++;
	assert(cnt <= 10'000);
	return asked[i] = ask(i);
}
int solve(int l, int r) {
	while (l <= r && get(l)[0] + get(l)[1] != get(r)[0] + get(r)[1]) {
		vector<int> vl = get(l), vr = get(r);
		if (vl[0] + vl[1] < vr[0] + vr[1]) {
			if (vl[0] + vl[1] == 0) {
				return l;
			}
			l++;
		} else {
			if (vr[0] + vr[1] == 0) {
				return r;
			}
			r--;
		}
	}
	if (l > r) return -1;
	vector<int> vl = get(l), vr = get(r);
	if (vl == vr) {
		vector<int> v = get(l);
		if (v[0] + v[1] == 0) {
			return l;
		}
		return -1;
	}
	return max(solve(l, (l + r) / 2), solve((l + r) / 2 + 1, r));
}
int find_best(int n) {
	return solve(0, n - 1);
}

• Subtask 1: 20 / 20
• Subtask 2: 70 / 80