#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
constexpr int lim = 80;
int count_mushrooms(int n) {
vector<int> a = {0}, b, s;
if (use_machine({0, 1}) == 0) {
a.push_back(1);
} else {
b.push_back(1);
}
if (n == 2) {
return a.size();
}
if (use_machine({0, 2}) == 0) {
a.push_back(2);
} else {
b.push_back(2);
}
for (int i = 3; i < n; i++) {
s.push_back(i);
}
vector<int> w = (a.size() > b.size() ? a : b);
bool is = (a == w);
while (max(a.size(), b.size()) < lim && s.size() > 1) {
int x = s.back(); s.pop_back();
int y = s.back(); s.pop_back();
int ret = use_machine({w[0], x, w[1], y});
if (is) {
if (ret == 0) {
a.push_back(x);
a.push_back(y);
} else if (ret == 1) {
a.push_back(x);
b.push_back(y);
} else if (ret == 2) {
b.push_back(x);
a.push_back(y);
} else {
b.push_back(x);
b.push_back(y);
}
} else {
if (ret == 0) {
b.push_back(x);
b.push_back(y);
} else if (ret == 1) {
b.push_back(x);
a.push_back(y);
} else if (ret == 2) {
a.push_back(x);
b.push_back(y);
} else {
a.push_back(x);
a.push_back(y);
}
}
}
int res = a.size();
while (!s.empty()) {
vector<int> k = (a.size() > b.size() ? a : b);
int m = min(k.size(), s.size());
vector<int> t, v;
for (int i = 0; i < m; i++) {
t.push_back(k[i]);
t.push_back(s.back());
v.push_back(s.back());
s.pop_back();
}
int cnt = use_machine(t);
if (a == k) {
if (cnt & 1) {
b.push_back(v.back());
} else {
a.push_back(v.back());
}
res += m - (cnt + 1) / 2;
} else {
if (cnt & 1) {
a.push_back(v.back());
} else {
b.push_back(v.back());
}
res += (cnt + 1) / 2;
}
}
return res;
}
