#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
constexpr int lim = 120;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
int count_mushrooms(int n) {
int res = 1;
vector<int> a = {0}, b, s;
for (int i = 1; i < n; i++) {
s.push_back(i);
}
shuffle(s.begin(), s.end(), rng);
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({0, x, y});
if (ret == 0) {
res += 2;
a.push_back(x);
a.push_back(y);
} else if (ret == 2) {
a.push_back(y);
b.push_back(x);
res++;
} else {
b.push_back(y);
if (use_machine({0, x}) == 0) {
res++;
a.push_back(x);
} else {
b.push_back(x);
}
}
}
while (!s.empty()) {
vector<int> k = (a.size() > b.size() ? a : b);
int mx = k.size();
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 == 0) {
a.insert(a.end(), v.begin(), v.end());
}
if (cnt & 1) {
b.push_back(v.back());
}
res += m - (cnt + 1) / 2;
} else {
if (cnt == 0) {
b.insert(b.end(), v.begin(), v.end());
}
if (cnt & 1) {
a.push_back(v.back());
}
res += (cnt + 1) / 2;
}
}
return res;
}
