#include "mushrooms.h"
#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
int count_mushrooms(int n)
{
vi m;
// 0 for a and 1 for b
vvi sure(2);
vi cnt(2, 0);
sure[0].push_back(0);
cnt[0] = 1;
int idx = 1;
while (idx < n && max(sz(sure[0]), sz(sure[1])) < 2)
{
assert(sz(sure[0]) > 0);
m.clear();
m.push_back(sure[0].front());
m.push_back(idx++);
int c1 = use_machine(m);
++cnt[c1], sure[c1].push_back(m.back());
}
while (idx < n && max(sz(sure[0]), sz(sure[1])) < sqrt(n) - 1)
{
int i = (sz(sure[0]) < sz(sure[1]));
m.clear();
for (int j = 0; j < 2; ++j)
{
m.push_back(sure[i][j]);
if (idx < n)
m.push_back(idx++);
}
int c2 = use_machine(m);
++cnt[i ^ (c2 / 2)], sure[i ^ (c2 / 2)].push_back(m[1]);
if (sz(m) > 3)
++cnt[i ^ (c2 & 1)], sure[i ^ (c2 & 1)].push_back(m[3]);
}
while (idx < n)
{
int i = (sz(sure[0]) < sz(sure[1]));
m.clear();
for (int j = 0; j < sz(sure[i]) && idx < n; ++j)
{
m.push_back(sure[i][j]);
m.push_back(idx++);
}
int c3 = use_machine(m);
int lenCnt = (sz(m) - 2) / 2;
cnt[i] += lenCnt - (c3 / 2);
cnt[i ^ 1] += c3 / 2;
++cnt[i ^ (c3 & 1)], sure[i ^ (c3 & 1)].push_back(m.back());
}
return cnt[0];
}
