Submission #1256072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256072		gelastropod	The Big Prize (IOI17_prize)	C++20	95.19 / 100	21 ms	2224 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

int find_best(int n) {
	// 5 types!
	vector<pair<int, int>> cache(n, { -1, -1 });
	set<int> found;
	int lolpop = 0;
	for (int i = 0; i < min(n, 474); i++) {
		auto j = ask(i);
		cache[i] = { j[0], j[1] };
		lolpop = max(lolpop, j[0] + j[1]);
		if (j[0] + j[1] == 0) return i;
		found.insert(i);
	}
	int crnt = 0;
	while (crnt < n) {
		auto qry = cache[crnt];
		if (qry.first == -1) {
			found.insert(crnt);
			auto j = ask(crnt);
			qry = { j[0], j[1] };
			cache[crnt] = qry;
		}
		if (qry.first + qry.second == 0) return crnt;
		if (qry.first + qry.second == lolpop) break;
		crnt++;
	}
	while (crnt < n) {
		auto crntval = cache[crnt];
		if (crntval.first == -1) {
			found.insert(crnt);
			auto j = ask(crnt);
			crntval = { j[0], j[1] };
			cache[crnt] = crntval;
		}
		int low = crnt, high = n - 1, ans = crnt;
		for (int i : found) {
			if (cache[i].second == crntval.second) {
				low = max(low, i);
			}
			if (i > crnt && cache[i].second != crntval.second) {
				high = min(high, i);
			}
		}
		while (low <= high) {
			int x = (low + high) / 2;
			pair<int, int> qry = cache[x];
			if (qry.first == -1) {
				found.insert(x);
				auto j = ask(x);
				qry = { j[0], j[1] };
				cache[x] = qry;
			}
			if (qry.first + qry.second == 0) return x;
			if (qry.first == 0 && qry.second == 1) {
			  ans = x;
			  break;
			}
			if (qry.second != crntval.second) {
				high = x - 1;
			}
			else {
				low = x + 1;
				ans = x;
			}
		}
		crnt = ans + 1;
		while (crnt < n) {
			auto qry = cache[crnt];
			if (qry.first == -1) {
				found.insert(crnt);
				auto j = ask(crnt);
				qry = { j[0], j[1] };
				cache[crnt] = qry;
			}
			if (qry.first + qry.second == 0) return crnt;
			if (qry.first + qry.second == lolpop) break;
			crnt++;
		}
	}
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
   83 | }
      | ^

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