#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int K = 150;
int count_mushrooms(int n) {
vector <int> a;
for (int i = 1; i < n; i++)
a.push_back(i);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
shuffle(a.begin(), a.end(), rng);
int ans = 1;
vector <int> A = {0}, B;
while (!a.empty()) {
vector <int> v;
int mx = max ((int)A.size(), (int)B.size());
if (mx == 1 || (int)A.size() + (int)B.size() >= K * 2 || (int)a.size() < 2) {
if ((int)A.size() >= (int)B.size()) {
int t = 0;
for (int i = 0; i < (int) A.size() && !a.empty(); i++) {
t++;
v.push_back(a.back());
v.push_back(A[i]);
a.pop_back();
}
int k = use_machine (v);
if (k % 2)
B.push_back(v[0]);
else
A.push_back(v[0]);
k = t - ((k + 1) / 2);
ans += k;
} else {
int t = 0;
for (int i = 0; i < (int) B.size() && !a.empty(); i++) {
t++;
v.push_back(a.back());
v.push_back(B[i]);
a.pop_back();
}
int k = use_machine (v);
if (k % 2)
A.push_back(v[0]);
else
B.push_back(v[0]);
k = ((k + 1) / 2);
ans += k;
}
} else {
int sz = (int)a.size();
if ((int)A.size() >= 2) {
int k = use_machine ({A[0], a[sz - 2], A[1], a[sz - 1]});
if (k >= 2) {
B.push_back(a[sz - 2]);
} else {
ans++;
A.push_back(a[sz - 2]);
}
if (k % 2 == 0) {
A.push_back(a[sz - 1]);
ans++;
} else {
B.push_back(a[sz - 1]);
}
} else {
int k = use_machine ({B[0], a[sz - 2], B[1], a[sz - 1]});
if (k >= 2) {
A.push_back(a[sz - 2]);
ans++;
} else {
B.push_back(a[sz - 2]);
}
if (k % 2 == 0) {
B.push_back(a[sz - 1]);
} else {
ans++;
A.push_back(a[sz - 1]);
}
}
a.pop_back();
a.pop_back();
}
}
return ans;
}
