#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n)
{
// what is my idea for subtask 2
// find the next A (after the first A)
// for each pair of 2 indices, I will write it as
// A x A y
// if the answer is 1, cnt++
// if the anser is 0, cnt += 2
// otherwise, do nothing
// now, let's optimize this
// I will think of smth like using sqrt
const int BLK = 183;
vector<int> a, b;
a.push_back(0);
if (n <= BLK)
{
for (int i = 1; i < min(n, BLK); i++)
{
if (use_machine({0, i}) == 1)
b.push_back(i);
else
a.push_back(i);
}
return (int)a.size();
}
int v2 = use_machine({0, 1}) == 1;
int v3 = use_machine({0, 2}) == 1;
if (v2)
b.push_back(1);
else
a.push_back(1);
if (v3)
b.push_back(2);
else
a.push_back(2);
for (int i = 3; i + 1 < min(n, BLK); i += 2)
{
if ((int)a.size() >= 2)
{
int y = use_machine({i, a.front(), i + 1, a.back()});
if (y == 0)
{
a.push_back(i);
a.push_back(i + 1);
}
else if (y == 1)
{
a.push_back(i + 1);
b.push_back(i);
}
else if (y == 2)
{
a.push_back(i);
b.push_back(i + 1);
}
else if (y == 3)
{
b.push_back(i);
b.push_back(i + 1);
}
}
else
{
int y = use_machine({i, b.front(), i + 1, b.back()});
if (y == 0)
{
b.push_back(i);
b.push_back(i + 1);
}
else if (y == 1)
{
a.push_back(i);
b.push_back(i + 1);
}
else if (y == 2)
{
a.push_back(i + 1);
b.push_back(i);
}
else if (y == 3)
{
a.push_back(i);
a.push_back(i + 1);
}
}
}
int res = (int)a.size();
for (int i = BLK; i < n;)
{
if ((int)a.size() > (int)b.size())
{
vector<int> m;
int j = min(n, i + (int)a.size());
int tmp = i;
int x = 0;
while (i < j)
{
m.push_back(a[x++]);
m.push_back(i++);
}
int y = use_machine(m);
if (!(y & 1))
{
res++;
a.push_back(m.back());
}
else
{
b.push_back(m.back());
y--;
}
int bad = (j - tmp - 1) * 2;
res += (bad - y) / 2;
}
else
{
vector<int> m;
int j = min(n, i + (int)b.size());
int tmp = i;
int x = 0;
while (i < j)
{
m.push_back(b[x++]);
m.push_back(i++);
}
int y = use_machine(m);
if (y & 1)
{
a.push_back(m.back());
res++;
y--;
}
else
{
b.push_back(m.back());
}
int bad = (j - tmp - 1) * 2;
res += y / 2;
}
}
return res;
}
