Submission #436610

#	Time	Username	Problem	Language	Result	Execution time	Memory
436610		frodakcin	Counting Mushrooms (IOI20_mushrooms)	C++17	80.71 / 100	11 ms	420 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())
		{
			int qv=0;
			for(size_t j=0;j<b.size() && i<n;++j, ++i)
				m.push_back(b[j]), m.push_back(i), ++qv;
			int v = use_machine(m);
			m.clear();

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

			if(v/2 == 0)
				for(int j=i-qv;j<i-1;++j)
					b.push_back(j);
			else if(v/2 == qv-1)
				for(int j=i-qv;j<i-1;++j)
					a.push_back(j);
			else
				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();


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

			if(v/2 == 0)
				for(int j=i-qv;j<i-1;++j)
					a.push_back(j);
			else if(v/2 == qv-1)
				for(int j=i-qv;j<i-1;++j)
					b.push_back(j);
			else
				ans += (qv-1)-v/2;
		}

	return a.size()+ans;
}

• Subtask 1: 80.7143 / 100