Submission #436513

#	Time	Username	Problem	Language	Result	Execution time	Memory
436513		frodakcin	Counting Mushrooms (IOI20_mushrooms)	C++17	80.71 / 100	14 ms	452 KiB

mushrooms

#include "mushrooms.h"
#include <cstdio>

int count_mushrooms(int n)
{
	std::vector<int> m, a, b;
	a.push_back(0);

	int ans=0;
	for(int i=1;i<n;)
		if(a.size() < b.size())
		{
			for(size_t j=0;j<b.size() && i<n;++j, ++i)
				m.push_back(b[j]), m.push_back(i);
			int v = use_machine(m);
			m.clear();

			if(v&1) a.push_back(i-1);
			else b.push_back(i-1);

			ans += v/2;
		}
		else
		{
			int qv=0;
			for(size_t j=0;j<a.size() && i<n;++j, ++i)
				m.push_back(a[j]), m.push_back(i), ++qv;
			int v = use_machine(m);
			m.clear();

			ans += (qv-1)-v/2;

			if(v&1) b.push_back(i-1);
			else a.push_back(i-1);
		}

	return a.size()+ans;
}

• Subtask 1: 80.7143 / 100