#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
constexpr int lim = 100;
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());
// }
res += m - (cnt + 1) / 2;
} else {
// if (cnt == 0) {
// b.insert(b.end(), v.begin(), v.end());
// }
res += (cnt + 1) / 2;
}
if (max(a.size(), b.size()) < lim) {
for (auto x : v) {
if (use_machine({0, x}) == 0) {
a.push_back(x);
} else {
b.push_back(x);
}
}
}
}
return res;
}
