제출 #548671

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
548671		blue	커다란 상품 (IOI17_prize)	C++17	0 / 100	12 ms	11556 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 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;

	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;
		}
	}

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

	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);
}

const int mxq = 5'000;
const int threshold = 450;

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++)
	{
		compute(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;

	int ind2 = 0;

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

		if(ans[i][0] + ans[i][1] == prizecount)
		{
			ind2 = i;
			break;
		}
	}

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

	solve(ind+1, ind2-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