Submission #346089

#	Time	Username	Problem	Language	Result	Execution time	Memory
346089		athensclub	Counting Mushrooms (IOI20_mushrooms)	C++14	63.31 / 100	12 ms	508 KiB

mushrooms

#include "mushrooms.h"
#include <vector>
#include <algorithm>
const int chunkSize = 137;

int div2RoundUp(int x)
{
	int d = x / 2;
	if (d * 2 < x)
		return d + 1;
	return d;
}

int count_mushrooms(int n)
{
	using namespace std;
	vector<int> aIndex = {0}, bIndex;
	std::vector<int> m;
	if (n == 1)
		return 1;

	if (n == 2)
	{
		m = {0, 1};
		int a = use_machine(m);
		if (a == 0)
			return 2;
		else
			return 1;
	}

	m = {0, 1};
	int a = use_machine(m);
	if (a == 0)
		aIndex.push_back(1);
	else
		bIndex.push_back(1);
	m = {0, 2};
	a = use_machine(m);
	if (a == 0)
		aIndex.push_back(2);
	else
		bIndex.push_back(2);

	for (int i = 3; i < min(chunkSize, n); i += 2)
	{
		if (i + 1 < min(chunkSize, n))
		{
			if (bIndex.size() >= 2)
			{
				// use _B_B
				m = {i, bIndex[0], i + 1, bIndex[1]};
				a = use_machine(m);
				switch (a)
				{
				case 0:
					bIndex.push_back(i);
					bIndex.push_back(i + 1);
					break;
				case 1:
					aIndex.push_back(i);
					bIndex.push_back(i + 1);
					break;
				case 2:
					bIndex.push_back(i);
					aIndex.push_back(i + 1);
					break;
				case 3:
					aIndex.push_back(i);
					aIndex.push_back(i + 1);
					break;
				}
			}
			else
			{
				// use _A_A
				m = {i, aIndex[0], i + 1, aIndex[1]};
				a = use_machine(m);
				switch (a)
				{
				case 0:
					aIndex.push_back(i);
					aIndex.push_back(i + 1);
					break;
				case 1:
					bIndex.push_back(i);
					aIndex.push_back(i + 1);
					break;
				case 2:
					aIndex.push_back(i);
					bIndex.push_back(i + 1);
					break;
				case 3:
					bIndex.push_back(i);
					bIndex.push_back(i + 1);
					break;
				}
			}
		}
		else
		{
			m = {0, i};
			a = use_machine(m);
			if (a == 0)
				aIndex.push_back(i);
			else
				bIndex.push_back(i);
		}
	}

	int aCount = 0;
	int len = max(aIndex.size(), bIndex.size());
	for (int i = chunkSize; i < n; i += len)
	{
		if (aIndex.size() > bIndex.size())
		{
			// use A_A_A_...
			m.clear();
			for (int j = 0; j < min(n - i, (int)aIndex.size()); j++)
			{
				m.push_back(aIndex[j]);
				m.push_back(i + j);
			}
			a = use_machine(m);
			aCount += min(n - i, (int)aIndex.size()) - div2RoundUp(a);
		}
		else
		{
			// use B_B_B_...
			m.clear();
			for (int j = 0; j < min(n - i, (int)bIndex.size()); j++)
			{
				m.push_back(bIndex[j]);
				m.push_back(i + j);
			}
			a = use_machine(m);
			aCount += div2RoundUp(a);
		}
	}

	return aCount + aIndex.size();
}

• Subtask 1: 63.3053 / 100