Submission #1204298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204298		borisAngelov	Counting Mushrooms (IOI20_mushrooms)	C++20	0 / 100	1 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 = 300;
	
	int good1, good2;
	int res1 = use_machine({0, 1});
	int res2 = use_machine({0, 2});
	
	if (res1 == 0)
	{
		good1 = 0;
		good2 = 1;
		type0.push_back(0);
		type0.push_back(1);
	}
	else if (res2 == 0)
	{
		good1 = 0;
		good2 = 2;
		type0.push_back(0);
		type0.push_back(2);
		type1.push_back(1);
	}
	else
	{
		good1 = 1;
		good2 = 2;
		type0.push_back(0);
		type1.push_back(1);
		type1.push_back(2);
	}
	
	for (int i = 3; i <= BUCKET_SIZE; i += 2)
	{
		int curr = use_machine({good1, i, good2, i + 1});
		if (curr == 0)
		{
			if (good1 == 1)
			{
				type1.push_back(i);
				type1.push_back(i + 1);
			}
			else
			{
				type0.push_back(i);
				type0.push_back(i + 1);
			}
		}
		else if (curr == 1)
		{
			if (good1 == 1)
			{
				type0.push_back(i + 1);
				type1.push_back(i);
			}
			else
			{
				type0.push_back(i);
				type1.push_back(i + 1);
			}
		}
		else if (curr == 2)
		{
			if (good1 == 1)
			{
				type0.push_back(i);
				type1.push_back(i + 1);
			}
			else
			{
				type0.push_back(i + 1);
				type1.push_back(i);
			}
		}
		else
		{
			if (good1 == 1)
			{
				type0.push_back(i);
				type0.push_back(i + 1);
			}
			else
			{
				type1.push_back(i);
				type1.push_back(i + 1);
			}
		}
	}

	int ans = 0;

	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: 0 / 100