Submission #1240385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240385		MuhammadSaram	Counting Mushrooms (IOI20_mushrooms)	C++20	53.94 / 100	4 ms	676 KiB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>

using namespace std;

const int M = 20000;

int ind[M];

int get(vector<int> v)
{
	for (int i=0;i<v.size();i++)
		v[i]=ind[v[i]];
	return use_machine(v);
}

int count_mushrooms(int n)
{
	vector<int> v={0},v1;
	vector<int> sh;
	for (int i=1;i<n;i++)
		sh.push_back(i);
	mt19937 rng(369);
	shuffle(sh.begin(),sh.end(),rng);
	for (int i=1;i<n;i++)
		ind[i]=sh[i-1];
	int j=n;
	for (int i=1;i<n;i+=2)
	{
		int mx=max(v.size(),v1.size());
		if (mx*mx>=n-i)
		{
			j=i;
			break;
		}
		int x=get({i+1,0,i});
		if (x==0)
			v.push_back(i), v.push_back(i+1);
		else if(x==2)
			v1.push_back(i), v1.push_back(i+1);
		else
		{
			if (get({i+1,0}))
				v.push_back(i), v1.push_back(i+1);
			else
				v.push_back(i+1), v1.push_back(i);
		}
	}
	bool b=0;
	int ans=v.size();
	if (v.size()<v1.size())
		swap(v,v1), b=1;
	int m=v.size();
	for (int it=j;it<n;it+=m)
	{
		vector<int> c;
		int id=0,tot=0;
		for (int l=it;l<min(n,it+m);l++)
			c.push_back(v[id++]), c.push_back(l), tot++;
		int x=get(c);
		if (b)
			ans+=(x+1)/2;
		else
			ans+=tot-(x+1)/2;
	}
	return ans;
}

• Subtask 1: 53.9379 / 100