#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int const mx=94;
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(783242309);
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];
}
