Submission #133474

#	Time	Username	Problem	Language	Result	Execution time	Memory
133474		hugo_pm	The Big Prize (IOI17_prize)	C++17	95.62 / 100	76 ms	5316 KiB

prize

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

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

int outil = -1;

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

#define ask flrfldl

int rp=-1;

void trouver(int a, int b, int va, int vb)
{
	if (a+1 >= b) return;
	if (b-a < 3) {
		for (int x = a; x < b; ++x) {
			if (realGet(x)[0] + realGet(x)[1] == 0) {
				rp = x;
				return;
			}
		}
		return;
	}

	int mid = (va + vb) / 2;
	int niceSp = -1;

	for (int split = mid; split < b; ++split) {
		auto res = realGet(split);
		int val = res[0] + res[1];
		if (val == 0) { rp = split; return; }
		if (val == outil) { niceSp = split; break; }
	}

	if (niceSp == -1) {
		for (int split = mid; split > a; --split) {
			auto res = realGet(split);
			int val = res[0] + res[1];
			if (val == 0) { rp = split; return; }
			if (val == outil) { niceSp = split; break; }
		}
	}

	if (niceSp != -1) {
		if (realGet(a)[0] != realGet(niceSp)[0]) {
			trouver(a, niceSp, a, min(mid, niceSp));
			if (rp != -1) return;
		}
		if (realGet(niceSp)[1] != realGet(b)[1]) {
			trouver(niceSp, b, max(mid, niceSp), b);
		}
	}
}

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(500, nbPrix);
	int lolId=-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;
		}
		if (val > 500) break;
	}

	int der = n-1;
	while (true) {
		auto res = realGet(der);
		int val = res[0] + res[1];
		if (val == 0) return der;
		if (val == outil) break;
		--der;
	}

	trouver(lolId, der, lolId, der);
	return rp;
}

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