Submission #1240340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240340		Muhammad_Aneeq	Counting Mushrooms (IOI20_mushrooms)	C++20	56.64 / 100	3 ms	452 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int const mx=90;
int count_mushrooms(int n) 
{
	if (n<=226)
	{
		int ans=0;
		for (int i=1;i<n;i++)
			ans+=(use_machine({0,i}));
		return n-ans;
	}
	mt19937 mt(784753459);
	vector<int>ind[2]={};
	ind[0].push_back(0);
	bool vis[n]={};
	vis[0]=1;
	while (max(ind[0].size(),ind[1].size())<mx)
	{
		int z=mt()%n;
		while (vis[z])
			z=mt()%n;
		vis[z]=1;
		ind[use_machine({0,z})].push_back(z);
	}
	vector<int>lef;
	bool w=0;
	if (ind[0].size()<ind[1].size())
	{
		swap(ind[0],ind[1]);
		w=1;
	}
	int cnt[2]={};
	for (auto i:{0,1})
		cnt[i]=ind[i].size();
	for (int i=0;i<n;i++)
	{
		if (vis[i]) continue;
		lef.push_back(i);
		if (lef.size()==mx)
		{
			vector<int>cur;
			for (int i=0;i<mx;i++)
			{
				cur.push_back(lef[i]);
				cur.push_back(ind[0][i]);
			}
			lef={};
			int g=use_machine(cur);
			int cn=(g+1)/2;	
			cnt[1]+=cn;
			cnt[0]+=mx-cn;
		}
	}
	if (lef.size())
	{
		int sz=lef.size();
		vector<int>cur;
		for (int i=0;i<sz;i++)
		{
			cur.push_back(lef[i]);
			cur.push_back(ind[0][i]);
		}
		lef={};
		int g=use_machine(cur);
		int cn=(g+1)/2;	
		cnt[1]+=cn;
		cnt[0]+=sz-cn;
	}
	return cnt[w];	
}

• Subtask 1: 56.6416 / 100