#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n){
mt19937 rng(177013);
int perm[n];
for(int i=0; i<n; i++) perm[i]=i;
shuffle(perm+1,perm+n,rng);
vector<int> r,b;
r.push_back(0);
int cur=1,ans=1;
while(cur<n){
if(r.size()>=b.size()){
vector<int> test;
for(int i=0; i<(int)r.size(); i++){
if(cur+i>=n) break;
test.push_back(perm[cur+i]);
test.push_back(r[i]);
}
int x=use_machine(test);
ans+=(int)test.size()/2-(x+1)/2;
if(x%2) b.push_back(perm[cur]);
else r.push_back(perm[cur]);
cur+=(int)test.size()/2;
}
else{
vector<int> test;
for(int i=0; i<(int)b.size(); i++){
if(cur+i>=n) break;
test.push_back(perm[cur+i]);
test.push_back(b[i]);
}
int x=use_machine(test);
ans+=(x+1)/2;
if(x%2) r.push_back(perm[cur]);
else b.push_back(perm[cur]);
cur+=(int)test.size()/2;
}
}
return ans;
}
