#include "mushrooms.h"
#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef long long ll;
//~ #define int ll
const int N = 20'000;
int count_mushrooms(int n){
vector<int> p[2];
p[0].push_back(0);
int B = 100;
//~ for(int i=1;i<=N;i++){
//~ if(2 * i + (N + i - 1) / i < 2 * B + (N + B - 1) / B){
//~ B = i;
//~ }
//~ }
int last = 1;
for(int i=1;i<n && max((int)p[0].size(), (int)p[1].size()) < B;i++){
last++;
if(use_machine({0, i})) p[1].push_back(i);
else p[0].push_back(i);
}
ar<int, 2> cc {};
cc[0] = p[0].size(), cc[1] = p[1].size();
for(int i=last;i<n;){
int B = p[0].size();
bool is = 1;
if((int)p[1].size() > B) is = 0, B = p[1].size();
int j = min(i + B, n);
vector<int> qq;
for(int k=i;k<j;k++){
qq.push_back(p[is ^ 1][k - i]);
qq.push_back(k);
}
int c = use_machine(qq);
if(c & 1) cc[is]++, p[is].push_back(j - 1), c--;
else cc[is ^ 1]++, p[is ^ 1].push_back(j - 1);
cc[is] += c / 2, cc[is ^ 1] += (j - i - 1 - c / 2);
i = j;
}
return cc[0];
}
