Submission #259188

#	Time	Username	Problem	Language	Result	Execution time	Memory
259188		GREGOIRELC	The Big Prize (IOI17_prize)	C++14	0 / 100	5 ms	444 KiB

prize

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

using namespace std;

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

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;
	vector<int> r = ask(N - 1);
	if(r[0] + r[1] < maxi)
	{
		estUtile[N - 1] = true;
	}
	dejaVu[N - 1] = true;
	resultGauche[N - 1] = r[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 borneGauche = curCadeau, borneDroite = N - 1;
		while(borneGauche < borneDroite - 1)
		{
			int mid = (borneGauche + borneDroite) / 2;
			if(estUtile[mid])
			{
				borneDroite = mid - 1;
			}
			else if(dejaVu[mid])
			{
				if(resultGauche[mid] == nbGauche)
				{
					borneGauche = mid;
				}
				else
				{
					borneDroite = mid - 1;
				}
			}
			else
			{
				r = ask(mid);
				dejaVu[mid] = true;
				resultGauche[mid] = r[0];
				if(r[0] + r[1] < maxi)
				{
					estUtile[mid] = true;
					borneDroite = mid - 1;
				}
				else if(r[0] > nbGauche)
				{
					borneDroite = mid - 1;
				}
				else
				{
					borneGauche = mid;
				}
			}
		}
		if(!estUtile[borneDroite] && resultGauche[borneDroite] == nbGauche)
		{
			curCadeau = borneDroite + 1;
		}
		else
		{
			curCadeau = borneGauche + 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: 0 / 20
• Subtask 2: 0 / 80