#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int count_mushrooms(int n) {
auto use = [&](vector<int> const&x){ return use_machine(x);};
vector<char> s(n);
// first find 2 equal ones
const int k = min(n, 3);
for(int i=1; i<k; ++i){
if(use({0, i})){
++s[i];
}
}
if(n == k){
return count(s.begin(), s.end(), 0);
}
// now find sqrt(n) equal ones
int i = k;
{
int me = 0;
if(2*accumulate(s.begin(), s.begin()+k, 0) > k){
me = 1;
}
vector<int> pool;
for(int j=0; j<k; ++j){
if(s[j] == me) pool.push_back(j);
}
assert(pool.size() >= 2);
const int l = min(n, k + int(1.1*sqrt(n)));
//debug << named(l) << "\n";
while(i<l && i+2 < n){
const int x = use({i, pool[0], i+1, pool[1]});
s[i] = me ^ (x%2==1);
s[i+1] = me ^ (x/2==1);
i += 2;
}
}
// now count
int ans = 0;
//debug << k << " : " << decltype(s)(s.begin(), s.begin()+i) << "\n";
{
array<vector<int>, 2> occ;
for(int j=0; j<i; ++j){
occ[s[j]].push_back(j);
}
//debug << named(occ) << "\n";
while(i < n){
const int me = (occ[1].size()>occ[0].size());
auto&pool = occ[me];
const int U = min<int>(n-i, occ[me].size()-1);
//const int U = min<int>(n-i, (occ[0].size()+occ[1].size()+1)/2-1);
vector<int> q(1, pool[0]);
for(int j=0; j<U; ++j){
q.push_back(i++);
q.push_back(pool[j+1]);
}
bool did = false;
if(i<n){
did = true;
q.push_back(i++);
}
int r = use(q);
if(did){
if(r%2 == 0){
occ[me].push_back(q.back());
} else {
occ[!me].push_back(q.back());
--r;
}
}
r /= 2;
if(me == 0) r = U-r;
ans += r;
}
ans += occ[0].size();
}
return ans;
}
