Submission #303579

#	Time	Username	Problem	Language	Result	Execution time	Memory
303579		tutis	버섯 세기 (IOI20_mushrooms)	C++17	75.59 / 100	17 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 = 0;
	vector<int>c;
	for (int i = sz; i < n; i++)
		c.push_back(i);
	while (c.size() > 0)
	{
		if (B.size() >= A.size())
		{
			int cnt = min((int)B.size(), (int)c.size());
			vector<int>m;
			for (int t = 0; t < cnt; t++)
			{
				m.push_back(c.back());
				c.pop_back();
				m.push_back(B[t]);
			}
			int a = use_machine(m);
			ans += (a + 1) / 2;
		}
		else
		{
			int cnt = min((int)A.size(), (int)c.size());
			vector<int>m;
			for (int t = 0; t < cnt; t++)
			{
				m.push_back(c.back());
				c.pop_back();
				m.push_back(A[t]);
			}
			int a = use_machine(m);
			ans += cnt - (a + 1) / 2;
		}
	}
	ans += (int)A.size();
	return ans;
}

• Subtask 1: 75.5853 / 100