Submission #148182

#	Time	Username	Problem	Language	Result	Execution time	Memory
148182		faremy	The Big Prize (IOI17_prize)	C++14	98.56 / 100	62 ms	1428 KiB

prize

#include "prize.h"


const int MAXN = 2e5 + 1;

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> ans = ask(middle);
	if (ans[0] + ans[1] == 0)
		return middle;

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

	if (ans[0] - sum(middle + 1) != 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)
{
	int nonLollipop = 0;
	for (int iBox = 0; iBox < std::min(474, n); iBox++)
	{
		std::vector<int> ans = ask(iBox);
		nonLollipop = std::max(nonLollipop, ans[0] + ans[1]);
	}

	int done = 0;
	for (int iBlock = 0; iBlock < n; iBlock += 474)
	{
		int end = std::min(iBlock + 474, n);
		std::vector<int> ans = ask(end - 1);

		int idk = 0;
		while (end != iBlock && ans[0] + ans[1] != nonLollipop)
		{
			if (ans[0] + ans[1] == 0)
				return end - 1;

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

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

		while (ans[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: 78.56 / 80