Submission #1204283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204283		borisAngelov	Counting Mushrooms (IOI20_mushrooms)	C++20	45.47 / 100	4 ms	432 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>

using namespace std;

int count_mushrooms(int n)
{
	if (n <= 226 * 2)
	{
		int ans = 1;

		for (int i = 1; i < n; i += 2)
		{
			if (i + 1 >= n) break;
			ans += 2 - use_machine({i, 0, i + 1});
		}

		if (n % 2 == 0) ans += 1 - use_machine({0, n - 1});

		return ans;
	}

	vector<int> type0, type1;
	const int BUCKET_SIZE = 400;
	
	for (int i = 1; i <= BUCKET_SIZE; i += 2)
	{
		int curr = use_machine({i, 0, i + 1});
		if (curr == 0)
		{
			type0.push_back(i);
			type0.push_back(i + 1);
		}
		else if (curr == 2)
		{
			type1.push_back(i);
			type1.push_back(i + 1);
		}
		else
		{
			if (use_machine({0, i}) == 0)
			{
				type0.push_back(i);
				type1.push_back(i + 1);
			}
			else
			{
				type0.push_back(i + 1);
				type1.push_back(i);
			}
		}
	}

	int ans = 1;

	if (type0.size() > type1.size())
	{
		ans += type0.size();

		vector<int> equalElements;
		equalElements.push_back(0);

		for (int i = 0; i < type0.size(); ++i)
		{
			equalElements.push_back(type0[i]);
		}

		int step = equalElements.size();

		for (int i = BUCKET_SIZE + 1; i < n; i = i + step)
		{
			int to = min(n - 1, i + step - 1);
			int len = to - i + 1;

			vector<int> myVector;

			for (int j = i; j <= to; ++j)
			{
				myVector.push_back(equalElements[j - i]);
				myVector.push_back(j);
			}

			int result = use_machine(myVector);
			int diff = (result % 2 == 1 ? result / 2 + 1 : result / 2);
			ans += len - diff;
		}
	}
	else
	{
		ans += type0.size();

		vector<int> equalElements;

		for (int i = 0; i < type1.size(); ++i)
		{
			equalElements.push_back(type1[i]);
		}

		int step = equalElements.size();

		for (int i = BUCKET_SIZE + 1; i < n; i = i + step)
		{
			int to = min(n - 1, i + step - 1);
			int len = to - i + 1;

			vector<int> myVector;

			for (int j = i; j <= to; ++j)
			{
				myVector.push_back(equalElements[j - i]);
				myVector.push_back(j);
			}

			int result = use_machine(myVector);
			int diff = (result % 2 == 1 ? result / 2 + 1 : result / 2);
			ans += diff;
		}
	}

	return ans;
}

• Subtask 1: 45.4728 / 100