#include <bits/stdc++.h>
#define pb push_back
#include "mushrooms.h"
using namespace std;
vector < int > a, b;
int base;
int count_mushrooms(int n)
{
base = 90;
a.pb(0);
vector < int > curr;
curr.pb(0);
curr.pb(1);
int fb = use_machine(curr);
if(fb)b.pb(1);
else a.pb(1);
if(n > 2)
{
curr.clear();
curr.pb(0);
curr.pb(2);
int fb = use_machine(curr);
if(fb)b.pb(2);
else a.pb(2);
}
else return a.size();
int i = 3;
while(i+1 < n && a.size() < base && b.size() < base)
{
if(a.size() >= 2)
{
vector < int > curr;
curr.pb(i);
curr.pb(a[0]);
curr.pb(i+1);
curr.pb(a[1]);
int fb = use_machine(curr);
if(fb % 2 == 1)b.pb(i);
else a.pb(i);
if(fb >= 2)b.pb(i+1);
else a.pb(i+1);
i += 2;
}
else
{
vector < int > curr;
curr.pb(i);
curr.pb(b[0]);
curr.pb(i+1);
curr.pb(b[1]);
int fb = use_machine(curr);
if(fb % 2 == 1)a.pb(i);
else b.pb(i);
if(fb >= 2)a.pb(i+1);
else b.pb(i+1);
i += 2;
}
}
/* for (auto x: a)
cout << x << " ";
cout << endl;
for (auto x: b)
cout << x << " " ;
cout << endl;*/
int cnta = a.size(), cntb = b.size();
while(i < n)
{
if(a.size() > b.size())
{
vector < int > addon;
for (int j = i; j < min(n, i + (int)a.size() - 1); ++ j)
addon.pb(j);
vector < int > curr;
int posa = 0;
for (auto x: addon)
{
curr.pb(x);
curr.pb(a[posa]);
posa ++;
}
// curr.pb(a[posa]);
int val = use_machine(curr);
cntb += (val/2 + val%2);
cnta += addon.size() - (val/2 + val%2);
if(val % 2 == 0)a.pb(i);
else b.pb(i);
i += addon.size();
}
else
{
vector < int > addon;
for (int j = i; j < min(n, i + (int)b.size() - 1); ++ j)
addon.pb(j);
vector < int > curr;
int posb = 0;
for (auto x: addon)
{
curr.pb(x);
curr.pb(b[posb]);
posb ++;
}
//curr.pb(b[posb]);
int val = use_machine(curr);
cnta += val/2 + val%2;
cntb += addon.size() - val/2 - (val%2);
if(val % 2 == 0)b.pb(i);
else a.pb(i);
i += addon.size();
}
}
assert(cnta + cntb == n);
return cnta;
}
