Submission #548675

#	Time	Username	Problem	Language	Result	Execution time	Memory
548675		blue	The Big Prize (IOI17_prize)	C++17	20 / 100	3063 ms	6176 KiB

prize

#include "prize.h"
#include <vector>
#include <iostream>
using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;


const int mx = 200'000;

int qrc = 0;

int n;
vi ans[mx], prize(mx, 0);
int prizecount;

void compute(int i)
{
	if(ans[i].empty())
	{
		qrc++;
		if(qrc == 10'000) while(1);
		ans[i] = ask(i);
	}
}

void solve(int l, int r)
{
	if(r < l) return;

	// cerr << "solve " << l << ' ' << r << '\n';

	int m = (l+r)/2;

	int lm = -1, rm = -1;

	for(int i = m; i >= l; i--)
	{
		compute(i);
		if(ans[i][0] + ans[i][1] == prizecount)
		{
			lm = i;
			break;
		}
	}

	for(int i = m; i <= r; i++)
	{
		compute(i);
		if(ans[i][0] + ans[i][1] == prizecount)
		{
			rm = i;
			break;
		}
	}

	// cerr << m << ' ' << lm << ' ' << rm << '\n';


	if(lm >= 0)
		if(ans[lm][0] - ans[l-1][0] >= 1)
			solve(l, lm-1);

	if(rm >= 0)
		if(ans[r+1][0] - ans[rm][0] >= 1)
			solve(rm+1, r);

	if(lm == -1)
		lm = l-1;
	if(rm == -1)
		rm = r+1;

	for(int i = lm+1; i < rm; i++)
		prize[i] = 1;
}

const int threshold = 450; //a lollipop will be found in the first (threshold) elements.

int find_best(int n_)
{
	// cerr << "called\n";
	n = n_;

	int maxscore = -1;
	int ind = 0;

	for(int i = 0; i < min(threshold, n); i++)
	{
		compute(i);

		if(ans[i][0] + ans[i][1] > maxscore)
		{
			maxscore = ans[i][0] + ans[i][1];
			ind = i;
		}
	}

	// cerr << "A\n";

	// cerr << "ind = " << ind << '\n';

	for(int i = 0; i < ind; i++)
		prize[i] = 1;

	prizecount = maxscore;

	int ind2 = 0;
	// cerr << "B\n";

	for(int i = n-1; 1; i--)
	{
		compute(i);

		if(ans[i][0] + ans[i][1] == prizecount)
		{
			ind2 = i;
			break;
		}
	}
	// cerr << "ind2 = " << ind2 << '\n';
	// cerr << "C\n";

	for(int i = ind2+1; i < n; i++)
		prize[i] = 1;

	solve(ind+1, ind2-1);

	// cerr << "D\n";

	// for(int i = 0; i < n; i++) cerr << prize[i] << ' ';
	// 	cerr << '\n';

	for(int i = 0; i < n; i++)
		if(prize[i])
			if(ans[i][0] + ans[i][1] == 0)
				return i;

	return -1;
}

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