Submission #1169072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169072		MateiKing80	Counting Mushrooms (IOI20_mushrooms)	C++20	80.14 / 100	3 ms	416 KiB

mushrooms

#include "mushrooms.h"
using namespace std;

int x, y, q, l = 3, c, ans, z = 146;
vector <vector <int>> v(2);
vector <int> u;

int count_mushrooms(int n) 
{
	if (n == 2) 
		return 2 - use_machine({0, 1});
	v[0].push_back(0);
	v[use_machine({0, 1})].push_back(1);
	v[use_machine({0, 2})].push_back(2);
	if (v[1].size() >= 2) 
		x = 1;

	for (int i = 3; i < min(n - 1, 2 * z + 1); i += 2) 
	{
		q = use_machine({v[x][0], i, v[x][1], i + 1});
		v[(q / 2) ^ x].push_back(i);
		v[(q % 2) ^ x].push_back(i + 1);
		l = i + 2;
	}
	if (v[1].size() > v[0].size()) 
		y = 1;
	ans = v[0].size();

	while (l < n) 
	{
		u = {v[y][0]};
		c = 0;
		while (l < n && c < z) 
		{
			u.push_back(l++);
			u.push_back(v[y][++c]);
		}
		q = use_machine(u) / 2;
		ans += (y ? q : c - q);
	}
	return ans;
}

• Subtask 1: 80.1418 / 100