#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
// std::vector<int> m;
// for (int i = 0; i < n; i++)
// m.push_back(i);
// int c1 = use_machine(m);
// m = {0, 1};
// int c2 = use_machine(m);
// return c1+c2;
// if (n <= 5000){
// vector <int> a, b;
// a.push_back(0);
// int N = min(200, n);
// for (int i = 1; i < N; i++){
// vector <int> m = {0, i};
// int c = use_machine(m);
// if (c == 0) a.push_back(i);
// else b.push_back(i);
// }
// if (N == n) return a.size();
// int ans = 0;
// while (N < n){
// int x = min(N + 99, n - 1);
// int add = x - N + 1;
// if (a.size() >= 100){
// vector <int> m;
// for (int i = 0; i < add; i++){
// m.push_back(a[i]);
// m.push_back(N + i);
// }
// int c = use_machine(m);
// //every B will add 2, except for 1
// c++;
// int bb = c/2;
// int aa = add - bb;
// ans += aa;
// } else {
// assert(b.size() >= 100);
// vector <int> m;
// for (int i = 0; i < add; i++){
// m.push_back(b[i]);
// m.push_back(N + i);
// }
// int c = use_machine(m) + 1;
// ans += c/2;
// }
// N = x + 1;
// }
// return ans + a.size();
// }
vector <int> a, b;
a.push_back(0);
int p = 1;
int ans = 0;
while (p < n){
if (a.size() > b.size()){
int g = a.size();
g = min(g, n - p);
vector <int> m;
for (int i = 0; i < g; i++){
m.push_back(p + i);
m.push_back(a[i]);
}
int c = use_machine(m);
if (c & 1) b.push_back(p), c--;
else a.push_back(p);
ans += g - c/2;
p += g;
} else {
int g = b.size();
g = min(g, n - p);
vector <int> m;
for (int i = 0; i < g; i++){
m.push_back(p + i);
m.push_back(b[i]);
}
int c = use_machine(m);
if (c & 1) a.push_back(p), c--;
else b.push_back(p);
ans += c/2;
p += g;
}
}
return ans + a.size();
}
