Submission #303625

#	Time	Username	Problem	Language	Result	Execution time	Memory
303625		tutis	Counting Mushrooms (IOI20_mushrooms)	C++17	92.62 / 100	13 ms	512 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 = 173;
	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;
}/*
int main()
{
	int n = 20000;
	for (int k = 5; k <= 300; k++)
	{
		int a = 2;
		int b = 1;
		int q = 2;
		int m = 2;
		for (int i = 3; i <= k; i += 2)
		{
			a++;
			b++;
			q++;
			m = i + 2;
		}
		int cnt = n - a - b;
		while (cnt > 0)
		{
			cnt -= max(a, b);
			if (a < b)
				a++;
			else
				b++;
			q++;
		}
		cout << k << " " << q << endl;
	}
}*/

• Subtask 1: 92.623 / 100