#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;
int rn=n;
int cb=b;
while(rn>0)
{
rn-=cb;
rn-=cb;
tot++;
tot++;
cb++;
}
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;
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);
cnt[(xp&1)^flp].push_back(i);
if(sz>1)
cnt[((xp&2)/2)^flp].push_back(i+1);
i+=sz;
}
int ans=cnt[0].size();
for(int i=p;i<n;)
{
int 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,um=use_machine(cur);
if(flp)
{
xp=((um+1)/2);
}
else
{
xp=(sz-((um+1)/2));
}
cnt[(um&1)^flp].push_back(i);
// 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;
}
