Submission #133465

#	Time	Username	Problem	Language	Result	Execution time	Memory
133465		hugo_pm	The Big Prize (IOI17_prize)	C++17	90 / 100	114 ms	5424 KiB

prize

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

int nbPrix;
vector<int> perm;
vector<int> rv[200*1005];

vector<int> realGet(int x)
{
	vector<int> &res = rv[x];
	if (res.empty()) res = ask(x);
	return res;
}

#define ask flrfldl

int find_best(int n)
{
	nbPrix = n;

	if (nbPrix <= 5000) {
		for (int i = 0; i < nbPrix; ++i) {
			auto res = realGet(i);
			if (res[0] + res[1] == 0) return i;
		}
	}
	
	int lim = min(800, nbPrix);
	int lolId=-1, outil=-1;

	for (int pos = 0; pos < lim; ++pos) {
		auto res = realGet(pos);
		int val = res[0] + res[1];
		if (val > outil) {
			lolId = pos;
			outil = val;
		}
		if (val == 0) {
			return pos;
		}
	}

	while (true) {
		int curLeft = realGet(lolId)[0];
		int lo = lolId, ri = nbPrix-1;

		while (lo < ri) {
			int mid = (lo+ri) / 2;
			int valMid = realGet(mid)[0];
			int valTot = valMid + realGet(mid)[1];
			if (valTot != outil || valMid != curLeft) ri = mid;
			else lo = mid+1;
		}


		int curPos = lo;
		while (true) {
			auto res = realGet(curPos);
			int val = res[0] + res[1];
			if (val == 0) return curPos;
			if (val == outil) {
				lolId = curPos;
				break;
			}
			++curPos;
		}
	}

}

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