Submission #259177

#	Time	Username	Problem	Language	Result	Execution time	Memory
259177		GREGOIRELC	The Big Prize (IOI17_prize)	C++14	20 / 100	118 ms	1528 KiB

prize

#include "prize.h"
#include <iostream>

using namespace std;

const int MAX_CADEAU = 2e5;
const int MAX_UTILE = 1000;

bool estUtile[MAX_CADEAU];
bool dejaVu[MAX_CADEAU];
int resultGauche[MAX_CADEAU];

int find_best(int N)
{
	int maxi = 0;
	for(int iCadeau = 0; iCadeau < min(MAX_UTILE, N); iCadeau++)
	{
		vector<int> r = ask(iCadeau);
		maxi = max(maxi, r[0] + r[1]);
	}

	int curCadeau = 0;
	while(curCadeau < N)
	{
		if(estUtile[curCadeau])
		{
			curCadeau++;
			continue;
		}
		vector<int> r;
		int nbGauche;
		if(dejaVu[curCadeau])
		{
			nbGauche = resultGauche[curCadeau];
		}
		else
		{
			r = ask(curCadeau);
			if(r[0] + r[1] < maxi)
			{
				estUtile[curCadeau] = true;
				curCadeau++;
				continue;
			}
			dejaVu[curCadeau] = true;
			resultGauche[curCadeau] = r[0];
			nbGauche = r[0];
		}
		int borneDroite = min(N - 1, curCadeau + 100);
		while(curCadeau < borneDroite)
		{
			if(estUtile[borneDroite])
			{
				borneDroite--;
				continue;
			}
			if(dejaVu[borneDroite] && resultGauche[borneDroite] == nbGauche)
			{
				break;
			}
			if(dejaVu[borneDroite] && resultGauche[borneDroite] > nbGauche)
			{
				borneDroite = (curCadeau + borneDroite) / 2;
				continue;
			}
			r = ask(borneDroite);
			dejaVu[borneDroite] = true;
			resultGauche[borneDroite] = r[0];
			if(r[0] + r[1] < maxi)
			{
				estUtile[borneDroite] = true;
				borneDroite--;
				continue;
			}
			if(r[0] == nbGauche)
			{
				break;
			}
			else
			{
				borneDroite = (curCadeau + borneDroite) / 2;
			}
		}
		curCadeau = borneDroite + 1;
	}

	for(int curCadeau = 0; curCadeau < N; curCadeau++)
	{
		if(estUtile[curCadeau])
		{
			vector<int> r = ask(curCadeau);
			if(r[0] + r[1] == 0)
			{
				return curCadeau;
			}
		}
	}
	return -1;
}

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