Submission #987053

#	Time	Username	Problem	Language	Result	Execution time	Memory
987053		VMaksimoski008	The Big Prize (IOI17_prize)	C++17	90 / 100	60 ms	2132 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

pii memo[200005];

pii query(int p) {
	if(memo[p] != pii{ -1, -1 }) return memo[p];
	vector<int> res = ask(p);
	return memo[p] = { res[0], res[1] };
}

int sum(int p) { return query(p).first + query(p).second; }
int L(int p) { return query(p).first; }
int R(int p) { return query(p).second; }

int find_best(int n) {
	for(int i=0; i<n; i++) memo[i] = { -1, -1 };

	int curr = -1, mx = 0;
	set<int> s;
	for(int i=0; i<min(500, n); i++) {
		mx = max(mx, sum(i));
		if(sum(i) == 0) return i;
	}

	for(int i=1; i<=mx; i++) {
		int l=curr+1, r=n-1, pos=n-1;

		while(l <= r) {
			int mid = (l + r) / 2;
			if(sum(mid) == 0) return mid;

			if(sum(mid) == mx) {
				if(L(mid) >= i) pos = mid, r = mid - 1;
				else l = mid + 1;
			} else {
				pos = mid;
				r = mid - 1;
			}
		}
		
		curr = pos;
	}

	return 0;
}

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