제출 #148190

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
148190		faremy	커다란 상품 (IOI17_prize)	C++14	92.18 / 100	62 ms	1320 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, int end, int rm)
{
	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;
	}

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

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, end, ans[1]);
			if (pos != -1)
				return pos;
			done++;
		}

		done += idk;
	}

	return -1;
}

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