Submission #548666

#	Time	Username	Problem	Language	Result	Execution time	Memory
548666		blue	The Big Prize (IOI17_prize)	C++17	0 / 100	92 ms	5796 KiB

prize

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

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


const int mx = 200'000;

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

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

	int m = (l+r)/2;

	int leftcount = ans[l-1][0];

	int mm = -1;

	for(int k = m; k >= l; k--)
	{
		if(ans[k].empty())
			ans[k] = ask(k);

		if(ans[k][0] + ans[k][1] == prizecount)
		{
			mm = k;
			break;
		}
		else
		{
			prize[k] = 1;
		}
	}

	if(mm != -1)
	{
		int rightcount = ans[mm][0];

		if(rightcount - leftcount >= 1)
		{
			solve(l, mm-1);
		}
	}



	

	int mm2 = -1;

	for(int k2 = m; k2 <= r; k2++)
	{
		if(ans[k2].empty())
			ans[k2] = ask(k2);

		if(ans[k2][0] + ans[k2][1] == prizecount)
		{
			mm2 = k2;
			break;
		}
		else
		{
			prize[k2] = 1;
		}
	}

	if(mm2 != -1)
		solve(mm2+1, r);
}

const int mxq = 200'000;
const int threshold = 1000;

int find_best(int n_)
{
	n = n_;
	if(n <= mxq)
	{
		pii mn{5*n, -1};
		for(int i = 0; i < n; i++)
		{
			vi z = ask(i);
			mn = min(mn, {z[0] + z[1], i});
		}
		return mn.second;
	}

	int maxscore = -1;
	int ind = 0;


	for(int i = 0; i < threshold; i++)
	{
		ans[i] = ask(i);
		if(ans[i][0] + ans[i][1] > maxscore)
		{
			maxscore = ans[i][0] + ans[i][1];
			ind = i;
		}
	}

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

	prizecount = maxscore;

	solve(ind+1, n-1);

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

	return -1;
}

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