#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
std::vector<int> ind[2];
ind[0].push_back(0);
int ans=1;
for(int i=1;i<n;)
{
if(ind[0].size()>=ind[1].size())
{
vector<int> query;
int rem=min(n-i,(int)ind[0].size());
for(int j=0;j<rem;j++)
{
query.push_back(ind[0][j]);
query.push_back(i+j);
}
int x=use_machine(query);
int ones=(x+1)/2;
int zeros=rem-ones;
ans+=zeros;
if(x%2==1)
{
ind[1].push_back(i+rem-1);
}
else
{
ind[0].push_back(i+rem-1);
}
i+=rem;
}
else
{
vector<int> query;
int rem=min(n-i,(int)ind[1].size());
for(int j=0;j<rem;j++)
{
query.push_back(ind[1][j]);
query.push_back(i+j);
}
int x=use_machine(query);
int zeros=(x+1)/2;
ans+=zeros;
if(x%2==1)
{
ind[0].push_back(i+rem-1);
}
else
{
ind[1].push_back(i+rem-1);
}
i+=rem;
}
}
return ans;
}
