#include "mushrooms.h"
#include <bits/stdc++.h>
#include <random>
using namespace std;
int count_mushrooms(int n) {
if (n <= 227){
int res = 1;
for (int i = 1; i < n; i++){
res += use_machine({0, i}) == 0;
}
return res;
}
vector<int> p(n);
iota(p.begin(), p.end(), 0);
shuffle(p.begin() + 1, p.end(), std::mt19937(std::random_device()()));
vector<int> A = {0}, B;
int k = 80;
int i = 1;
while (i < 3){
if (use_machine({0, p[i]}) == 0) A.push_back(p[i]); else
B.push_back(p[i]);
i++;
}
if (A.size() >= 2){
int cnt = use_machine({A[0], p[i], A[1], p[i + 1]});
if (cnt & 2) B.push_back(p[i]); else
A.push_back(p[i]);
if (cnt & 1) B.push_back(p[i + 1]); else
A.push_back(p[i + 1]);
} else {
int cnt = use_machine({B[0], p[i], B[1], p[i + 1]});
if (cnt & 2) A.push_back(p[i]); else
B.push_back(p[i]);
if (cnt & 1) A.push_back(p[i + 1]); else
B.push_back(p[i + 1]);
}
i += 2;
while (i < 2 * k + 3){
if (A.size() >= 3){
int cnt = use_machine({A[0], p[i], A[1], p[i + 1], A[2], p[i + 2]});
if (cnt / 2 != 1){
if (cnt / 2 == 0) A.push_back(p[i]), A.push_back(p[i + 1]); else
B.push_back(p[i]), B.push_back(p[i + 1]);
} else {
if (use_machine({0, p[i]}) == 0) A.push_back(p[i]), B.push_back(p[i + 1]); else
B.push_back(p[i]), A.push_back(p[i + 1]);
}
if (cnt & 1) B.push_back(p[i + 2]); else
A.push_back(p[i + 2]);
} else {
int cnt = use_machine({B[0], p[i], B[1], p[i + 1], B[2], p[i + 2]});
if (cnt / 2 != 1){
if (cnt / 2 == 0) B.push_back(p[i]), B.push_back(p[i + 1]); else
A.push_back(p[i]), A.push_back(p[i + 1]);
} else {
if (use_machine({0, p[i]}) == 0) A.push_back(p[i]), B.push_back(p[i + 1]); else
B.push_back(p[i]), A.push_back(p[i + 1]);
}
if (cnt & 1) A.push_back(p[i + 2]); else
B.push_back(p[i + 2]);
}
i += 3;
}
int res = A.size();
while (i < n){
vector<int> r;
if (A.size() > B.size()){
for (int x : A){
if (i >= n) break;
r.push_back(x);
r.push_back(p[i]);
i++;
}
int cnt = use_machine(r);
if (cnt & 1) B.push_back(r.back()); else
A.push_back(r.back());
res += r.size() / 2 - (cnt + 1) / 2;
} else {
for (int x : B){
if (i >= n) break;
r.push_back(x);
r.push_back(p[i]);
i++;
}
int cnt = use_machine(r);
if (cnt & 1) A.push_back(r.back()); else
B.push_back(r.back());
res += (cnt + 1) / 2;
}
}
return res;
}
