#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
#define pb push_back
#define bk back()
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
mt19937 rng(127);
int count_mushrooms(int n) {
vi known[2];
vi untested;
int ans = 1;
known[0].pb(0);
for(int i = 1; i < n; i++){
untested.pb(i);
}
shuffle(all(untested), rng);
while(sz(untested)){
int better_ind = 0;
if(sz(known[1]) > sz(known[0])) better_ind = 1;
vi to_test;
int special = untested.bk; untested.pop_back();
to_test.pb(special);
to_test.pb(known[better_ind][0]);
vi tested;
for(int i = 1; i < min(sz(untested), sz(known[better_ind])); i++){
tested.pb(untested.bk);
to_test.pb(untested.bk); untested.pop_back();
to_test.pb(known[better_ind][i]);
}
int res = use_machine(to_test);
int special_identity = better_ind;
if(res % 2 == 0){
}
else{
special_identity^=1;
}
known[special_identity].pb(special);
if(special_identity == 0){
ans++;
}
// cout << res/2 << " " << sz(tested) << "\n";
if(res/2 == sz(tested)){
for(auto u: tested){
known[better_ind^1].pb(u);
}
}
else if(res/2 == 0){
for(auto u: tested){
known[better_ind].pb(u);
}
}
if(better_ind == 0){
ans+=sz(tested)-res/2;
}
else{
ans+=res/2;
}
}
return ans;
}
