Submission #148205

#	Time	Username	Problem	Language	Result	Execution time	Memory
148205		faremy	The Big Prize (IOI17_prize)	C++14	20 / 100	59 ms	6120 KiB

prize

#include "prize.h"


const int MAXN = 2e5 + 1;

std::vector<int> ans[MAXN];

bool off[MAXN];
int countOff[MAXN];


void add(int i)
{
	while (i <= MAXN)
	{
		countOff[i]++;
		i += i & (-i);
	}
}

int sum(int i)
{
	int res = 0;
	while (i > 0)
	{
		res += countOff[i];
		i -= i & (-i);
	}

	return res;
}

int searchgood(std::vector<int> space, int non)
{
	if (space.empty())
		return -1;
	int middle = space[space.size() / 2];

	std::vector<int> a = ask(middle);
	if (a[0] + a[1] == 0)
		return middle;

	if (a[0] + a[1] != non)
	{
		off[middle] = true;
		add(middle + 1);
		return -1;
	}

	if (a[0] - sum(middle) != 0)
		return searchgood(std::vector<int>(space.begin(), space.begin() + space.size() / 2), non);
	return searchgood(std::vector<int>(space.begin() + space.size() / 2 + 1, space.end()), non);
}

int find_best(int n)
{
	if (n < 474)
	{
		for (int i = 0; i < n; i++)
			if (ask(i)[0] + ask(i)[1] == 0)
				return i;
		return -1;
	}

	int step = n / 474;
	int nonLollipop = 0;

	for (int iBlock = 0; iBlock < n; iBlock += step)
	{
		ans[iBlock] = ask(std::min(iBlock + step, n) - 1);
		nonLollipop = std::max(nonLollipop, ans[iBlock][0] + ans[iBlock][1]);
	}

	int done = 0;
	for (int iBlock = 0; iBlock < n; iBlock += step)
	{
		int end = std::min(iBlock + step, n);
		int idk = 0;
		
		while (end != iBlock && ans[iBlock][0] + ans[iBlock][1] != nonLollipop)
		{
			if (ans[iBlock][0] + ans[iBlock][1] == 0)
				return end - 1;

			off[end - 1] = true;
			add(end);
			idk++;

			end--;
			ans[iBlock] = ask(end - 1);
		}
		
		if (end == iBlock)
		{
			done += idk;
			continue;
		}

		while (ans[iBlock][0] > done)
		{
			std::vector<int> sspace;
			for (int iBox = iBlock; iBox < end; iBox++)
				if (!off[iBox])
					sspace.emplace_back(iBox);

			int pos = searchgood(sspace, nonLollipop);
			if (pos != -1)
				return pos;
			done++;
		}

		done += idk;
	}

	return -1;
}

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