Submission #303584

#	Time	Username	Problem	Language	Result	Execution time	Memory
303584		tutis	Counting Mushrooms (IOI20_mushrooms)	C++17	91.87 / 100	14 ms	544 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
	vector<int>A, B;
	A.push_back(0);
	int sz = 200;
	for (int i = 1; i < sz && i < n; i++)
	{
		if (i + 1 < sz && i + 1 < n && i >= 3)
		{
			if (A.size() >= 2)
			{
				int c = use_machine({A[0], i, A[1], i + 1});
				if (c / 2 == 1)
					B.push_back(i);
				else
					A.push_back(i);
				if (c % 2 == 1)
					B.push_back(i + 1);
				else
					A.push_back(i + 1);
			}
			else
			{
				int c = use_machine({B[0], i, B[1], i + 1});
				if (c / 2 == 1)
					A.push_back(i);
				else
					B.push_back(i);
				if (c % 2 == 1)
					A.push_back(i + 1);
				else
					B.push_back(i + 1);
			}
			i++;
		}
		else {
			if (use_machine({0, i}) == 0)
				A.push_back(i);
			else
				B.push_back(i);
		}
	}
	int ans = A.size();
	vector<int>c;
	for (int i = sz; i < n; i++)
		c.push_back(i);
	while (c.size() > 0)
	{
		if ((int)B.size() >= (int)A.size())
		{
			int cnt = min((int)B.size(), (int)c.size());
			vector<int>m;
			for (int t = 0; t < cnt; t++)
			{
				m.push_back(B[t]);
				m.push_back(c.back());
				c.pop_back();
			}
			int a = use_machine(m);
			ans += (a + 1) / 2;
			if (a % 2 == 0)
				B.push_back(m.back());
			else
				A.push_back(m.back());
		}
		else
		{
			int cnt = min((int)A.size(), (int)c.size());
			vector<int>m;
			for (int t = 0; t < cnt; t++)
			{
				m.push_back(A[t]);
				m.push_back(c.back());
				c.pop_back();
			}
			int a = use_machine(m);
			ans += cnt - (a + 1) / 2;
			if (a % 2 == 0)
				A.push_back(m.back());
			else
				B.push_back(m.back());
		}
	}
	return ans;
}

• Subtask 1: 91.8699 / 100