Submission #1226418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226418		Mousa_Aboubaker	Counting Mushrooms (IOI20_mushrooms)	C++20	91.87 / 100	3 ms	444 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;

int count_mushrooms(int n)
{
	// what is my idea for subtask 2
	// find the next A (after the first A)
	// for each pair of 2 indices, I will write it as
	// A x A y
	// if the answer is 1, cnt++
	// if the anser is 0, cnt += 2
	// otherwise, do nothing

	// now, let's optimize this
	// I will think of smth like using sqrt

	const int BLK = 201;

	vector<int> a, b;
	a.push_back(0);
	if (n <= BLK)
	{
		for (int i = 1; i < min(n, BLK); i++)
		{
			if (use_machine({0, i}) == 1)
				b.push_back(i);
			else
				a.push_back(i);
		}
		return (int)a.size();
	}
	int v2 = use_machine({0, 1}) == 1;
	int v3 = use_machine({0, 2}) == 1;
	if (v2)
		b.push_back(1);
	else
		a.push_back(1);
	if (v3)
		b.push_back(2);
	else
		a.push_back(2);
	for (int i = 3; i + 1 < min(n, BLK); i += 2)
	{
		if ((int)a.size() >= 2)
		{
			int y = use_machine({i, a.front(), i + 1, a.back()});
			if (y == 0)
			{
				a.push_back(i);
				a.push_back(i + 1);
			}
			else if (y == 1)
			{
				a.push_back(i + 1);
				b.push_back(i);
			}
			else if (y == 2)
			{
				a.push_back(i);
				b.push_back(i + 1);
			}
			else if (y == 3)
			{
				b.push_back(i);
				b.push_back(i + 1);
			}
		}
		else
		{
			int y = use_machine({i, b.front(), i + 1, b.back()});
			if (y == 0)
			{
				b.push_back(i);
				b.push_back(i + 1);
			}
			else if (y == 1)
			{
				a.push_back(i);
				b.push_back(i + 1);
			}
			else if (y == 2)
			{
				a.push_back(i + 1);
				b.push_back(i);
			}
			else if (y == 3)
			{
				a.push_back(i);
				a.push_back(i + 1);
			}
		}
	}

	int res = (int)a.size();
	for (int i = BLK; i < n;)
	{
		if ((int)a.size() > (int)b.size())
		{
			vector<int> m;
			int j = min(n, i + (int)a.size());
			int tmp = i;
			int x = 0;
			while (i < j)
			{
				m.push_back(a[x++]);
				m.push_back(i++);
			}

			int y = use_machine(m);
			if (!(y & 1))
			{
				res++;
				a.push_back(m.back());
			}
			else
			{
				b.push_back(m.back());
				y--;
			}

			int bad = (j - tmp - 1) * 2;
			res += (bad - y) / 2;
		}
		else
		{
			vector<int> m;
			int j = min(n, i + (int)b.size());
			int tmp = i;
			int x = 0;
			while (i < j)
			{
				m.push_back(b[x++]);
				m.push_back(i++);
			}

			int y = use_machine(m);
			if (y & 1)
			{
				a.push_back(m.back());
				res++;
				y--;
			}
			else
			{
				b.push_back(m.back());
			}

			int bad = (j - tmp - 1) * 2;
			res += y / 2;
		}
	}

	return res;
}

• Subtask 1: 91.8699 / 100