#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int B=200;
int optb(int n)
{
int fnl=1e9,opt=1e9;
for(int b=1;b<=n;b++)
{
int tot=b+((n-b)/b);
if(tot<fnl)
{
fnl=tot;
opt=b;
}
}
// cout<<fnl<<' '<<opt<<endl;
// cout<<(22600/fnl)<<endl;
return opt;
}
int count_mushrooms(int n) {
if(n<=226)
{
int ans=1;
for(int i=1;i<n;i++)
{
ans+=!use_machine({0,i});
}
return ans;
}
// vector<int> ord(n);
// iota(begin(ord),end(ord),0);
// srand(time(0));
// random_shuffle(begin(ord),end(ord),rand);
vector<int> cnt[4];
cnt[0].push_back(0);
for(int i=1;i<=2;i++)
cnt[use_machine({0,i})].push_back(i);
int p=optb(n)+2;
// p-=(p%2==0);
for(int i=3;i<p;)
{
int flp=0;
if(cnt[0].size()<cnt[1].size())
{
flp=1;
}
vector<int> cur;
int sz=min(2,min((int)(cnt[flp].size()),p-i));
for(int j=0;j<sz;j++)
{
cur.push_back(i+j),cur.push_back(cnt[flp][j]);
}
int xp=use_machine(cur);
// if(xp&1)
{
cnt[(xp&1)^flp].push_back(i);
}
// if(xp&2)
if(sz>1)
{
cnt[((xp&2)/2)^flp].push_back(i+1);
}
i+=sz;
}
int ans=cnt[0].size();
// cout<<p<<endl;
// for(auto x:cnt[0])
// {
// cout<<x<<' ';
// }
// cout<<endl;
// for(auto x:cnt[1])
// {
// cout<<x<<' ';
// }
// cout<<endl;
for(int i=p;i<n;)
{
bool flp=0;
if(cnt[0].size()<cnt[1].size())
{
flp=1;
}
vector<int> cur;
int sz=min((int)(cnt[flp].size()),n-i);
for(int j=0;j<sz;j++)
{
cur.push_back(i+j),cur.push_back(cnt[flp][j]);
}
int xp=0;
if(flp)
{
xp=((use_machine(cur)+1)/2);
}
else
{
xp=(sz-((use_machine(cur)+1)/2));
}
if(xp==0)
{
// none is equal to one all are B
for(int j=0;j<sz;j++)
{
cnt[1].push_back(i+j);
}
}
if(xp==sz)
{
// all are A
for(int j=0;j<sz;j++)
{
cnt[0].push_back(i+j);
}
}
ans+=xp;
i+=sz;
}
return ans;
}
