#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;
}
