Submission #436629

#	Time	Username	Problem	Language	Result	Execution time	Memory
436629		frodakcin	Counting Mushrooms (IOI20_mushrooms)	C++17	91.87 / 100	11 ms	340 KiB

mushrooms

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

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

	if(n > 1000)
	{
		if(use_machine({0, i})==0)
			a.push_back(i); else b.push_back(i);
		++i;
		if(use_machine({0, i})==0)
			a.push_back(i); else b.push_back(i);
		++i;

		bool swapped=0;
		if(a.size() < b.size())
			std::swap(a,b), swapped=1;

		for(int j=0;j<100;++j)
		{
			int v = use_machine({a[0], i, a[1], i+1});
			if(v&1) b.push_back(i+1); else a.push_back(i+1);
			if(v&2) b.push_back(i); else a.push_back(i);
			i+=2;
		}

		if(swapped)
		std::swap(a, b);
	}

	int ans=0;
	for(;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: 91.8699 / 100