#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
mt19937 rng(time(0));
int K=82,p=322;
int count_mushrooms(int n){
int res=0;
vector<int>ind[2];ind[0].pb(0);
/*int i=1;
for(;i<min(3,n);i++){
vector<int>temp={0,i};
if(use_machine(temp)==0) ind[0].pb(i);
else ind[1].pb(i);
}
while(i+1<n&&max(ind[0].size(),ind[1].size())<K){
if(ind[0].size()>=2){
vector<int>temp={i,ind[0][0],i+1,ind[0][1]};
int x=use_machine(temp);
if(x==3) ind[1].pb(i),ind[1].pb(i+1);
if(x==2) ind[0].pb(i),ind[1].pb(i+1);
if(x==1) ind[1].pb(i),ind[0].pb(i+1);
if(x==0) ind[0].pb(i),ind[0].pb(i+1);
}
else{
vector<int>temp={i,ind[1][0],i+1,ind[1][1]};
int x=use_machine(temp);
if(x==3) ind[0].pb(i),ind[0].pb(i+1);
if(x==2) ind[1].pb(i),ind[0].pb(i+1);
if(x==1) ind[0].pb(i),ind[1].pb(i+1);
if(x==0) ind[1].pb(i),ind[1].pb(i+1);
}
i+=2;
}*/
for(int i=1;i<n;){
int r=rng()%1000;
if(r<=p&&i+1<n&&max(ind[0].size(),ind[1].size())>=2){
if(ind[0].size()>=2){
vector<int>temp={i,ind[0][0],i+1,ind[0][1]};
int x=use_machine(temp);
if(x==3) ind[1].pb(i),ind[1].pb(i+1);
if(x==2) ind[0].pb(i),ind[1].pb(i+1);
if(x==1) ind[1].pb(i),ind[0].pb(i+1);
if(x==0) ind[0].pb(i),ind[0].pb(i+1);
}
else{
vector<int>temp={i,ind[1][0],i+1,ind[1][1]};
int x=use_machine(temp);
if(x==3) ind[0].pb(i),ind[0].pb(i+1);
if(x==2) ind[1].pb(i),ind[0].pb(i+1);
if(x==1) ind[0].pb(i),ind[1].pb(i+1);
if(x==0) ind[1].pb(i),ind[1].pb(i+1);
}
i+=2;
}
else{
vector<int>temp;
if(ind[0].size()>=ind[1].size()){
int k=ind[0].size(),j=i;
for(int ct=0;i<n&&ct<k;i++,ct++){
temp.pb(i);
temp.pb(ind[0][ct]);
}
int x=use_machine(temp),sz=temp.size();
if(x%2==0) ind[0].pb(j),res--;
else ind[1].pb(j);
res+=sz-x>>1;
}
else{
int k=ind[1].size(),j=i;
for(int ct=0;i<n&&ct<k;i++,ct++){
temp.pb(i);
temp.pb(ind[1][ct]);
}
int x=use_machine(temp),sz=temp.size();
if(x%2==1) ind[0].pb(j),res--;
else ind[1].pb(j);
res+=x+1>>1;
}
}
}
res+=ind[0].size();
return res;
}
