#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
vector <int> a = { 0 }, b;
int nex = 1;
int count_mushrooms(int n) {
if (n == 2)
{
return 2 - use_machine({0, 1});
}
if (n == 3)
{
return 3 - use_machine({0, 1}) - use_machine({0, 2});
}
bool swapped = false;
int e = use_machine({0, 1});
if (e == 1) {
b.emplace_back(1);
e = use_machine({0, 2});
if (e) {
b.emplace_back(2);
swapped = true;
swap(a, b);
}
else a.emplace_back(2);
} else {
a.emplace_back(1);
}
nex = a.size() + b.size();
int wanted = min(n, (int)44);
// cout << "SWAP " << swapped << "\n";
while (max(a.size(), b.size()) < (size_t)wanted && a.size() + b.size() + max(a.size(), b.size()) < (size_t)n)
{
e = use_machine({a[0], nex, a[1], nex + 1});
switch (e)
{
case 0:
a.emplace_back(nex);
a.emplace_back(nex + 1);
break;
case 2:
a.emplace_back(nex + 1);
b.emplace_back(nex);
break;
case 1:
a.emplace_back(nex);
b.emplace_back(nex + 1);
break;
case 3:
b.emplace_back(nex);
b.emplace_back(nex + 1);
break;
default:
assert(0);
}
// cout << swapped << " " << a.size() << " " << b.size() << "\n";
nex += 2;
}
// cout << "\n";
// for (int i : a) cout << i << " ";
// cout << "\n";
// for (int i : b) cout << i << " ";
// cout << "\n";
if (a.size() + b.size() == (size_t)n)
{
if (swapped) return b.size();
else return a.size();
}
if (b.size() > a.size()) {
swap(a, b);
swapped ^= 1;
}
// cout << "SWAP " << swapped << "\n";
int seen = 0;
int b_count = 0;
vector <int> v(a.size() * 2), u(b.size() * 2);
for (size_t i = 0; i < a.size(); i++) v[i * 2] = a[i];
for (size_t i = 0; i < b.size(); i++) u[i * 2] = b[i];
while (nex + (int)a.size() < n)
{
for (size_t i = 0; i < a.size(); i++) v[i * 2 + 1] = nex++;
e = use_machine(v);
b_count += e / 2;
seen += a.size() - 1;
if (e & 1)
{
b.emplace_back(nex - 1);
u.emplace_back(nex - 1);
u.emplace_back(-1);
if (b.size() > a.size())
{
swap(a, b);
swap(u, v);
b_count = seen - b_count;
swapped ^=1;
}
} else {
a.emplace_back(nex - 1);
v.emplace_back(nex - 1);
v.emplace_back(-1);
}
}
// cout << n << " " << nex <<endl;
int c = nex;
if (n - nex != 0) {
vector <int> j((n - nex) * 2);
for (int i = 0; i < n - c; i++) j[i * 2] = a[i];
for (int i = 0; i < n - c; i++) j[i * 2 + 1] = nex++;
e = use_machine(j);
b_count += e / 2 + (e & 1);
}
if (swapped) return b_count + b.size();
else return n - (b_count + b.size());
}
