Submission #434585

#	Time	Username	Problem	Language	Result	Execution time	Memory
434585		arayi	Counting Mushrooms (IOI20_mushrooms)	C++17	90.76 / 100	11 ms	336 KiB

mushrooms

#include "mushrooms.h"
#include <iostream>
#include <vector>
#define ad push_back
using namespace std;
 
int n;
vector<int> a, b, p;
int sm;
int count_mushrooms(int n) 
{
	::n = n;
	if(n < 230)
	{
		p.ad(0);
		for (int i = 1; i < n; i++)
		{
			p.ad(i);
			if(use_machine(p) == 0) sm++;
			p.pop_back();
		}
		return sm + 1;
	}
	a.ad(0);
	p.ad(0); p.ad(1);
	if(use_machine(p)) b.ad(1);
	else a.ad(1);
	p.pop_back(); p.ad(2);
	if(use_machine(p)) b.ad(2);
	else a.ad(2);
	p.pop_back();
	int i;
	for (i = 3; i <= 230; i+=2)
	{
		p.clear();
		if(a.size() >= b.size())
		{
			p.ad(a[0]), p.ad(i);
			p.ad(a[1]), p.ad(i+1);
			int s = use_machine(p);
			if(s%2==1) b.ad(i+1);
			else a.ad(i+1);
			if(s>=2) b.ad(i);
			else a.ad(i);
		}
		else
		{
			p.ad(b[0]), p.ad(i);
			p.ad(b[1]), p.ad(i+1);
			int s = use_machine(p);
			if(s%2==1) a.ad(i+1);
			else b.ad(i+1);
			if(s>=2) a.ad(i);
			else b.ad(i);
		}
	}
	sm = a.size();
	for (;i < n;)
	{
		p.clear();
		if(a.size() >= b.size())
		{
			int k = min((int)a.size(), n-i);
			for (int j = 0; j < k; j++)
				p.ad(a[j]), p.ad(i+j);
			int s = use_machine(p);
			if(s%2==1) b.ad(i+k-1), s--;
			else a.ad(i+k-1), sm++;
			k--, s/=2; sm+=k-s; i+=k+1;
		}
		else
		{
			int k = min((int)b.size(), n-i);
			for (int j = 0; j < k; j++)
				p.ad(b[j]), p.ad(i+j);
			int s = use_machine(p);
			if(s%2==1) a.ad(i+k-1), s--, sm++;
			else b.ad(i+k-1);
			s/=2; sm+=s; i+=k;
		}
	}
	return sm;	
}

• Subtask 1: 90.7631 / 100