#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define vll vector<ll>
#define pll pair<ll, ll>
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef int ll;
const ll B=141;
int count_mushrooms(int n) {
if(n==2){
vll tep={0, 1};
ll re=use_machine(tep);
if(re==0){
return 2;
}
else{
return 1;
}
}
ll cnt[2]={};
ll ans[2]={};
array<vll, 2> v;
v[0].pb(0);
cnt[0]++;
ans[0]++;
for(ll i=1;i<=2;i++){
vll tep;
tep.pb(0);
tep.pb(i);
ll re=use_machine(tep);
cnt[re]++;
ans[re]++;
v[re].pb(i);
}
for(ll i=3;i<n && i<2*B;i+=2){
vll tep;
if(cnt[0]>=2){
tep.pb(v[0][0]);
tep.pb(i);
tep.pb(v[0][1]);
if(i+1<n) tep.pb(i+1);
ll re=use_machine(tep);
cnt[((re>>1)&1)]++;
ans[((re>>1)&1)]++;
v[((re>>1)&1)].pb(i);
if(i+1<n){
cnt[(re&1)]++;
ans[(re&1)]++;
v[(re&1)].pb(i+1);
}
}
else{
tep.pb(v[1][0]);
tep.pb(i);
tep.pb(v[1][1]);
if(i+1<n) tep.pb(i+1);
ll re=use_machine(tep);
cnt[((re>>1)&1)^1]++;
ans[((re>>1)&1)^1]++;
v[((re>>1)&1)^1].pb(i);
if(i+1<n){
cnt[(re&1)^1]++;
ans[(re&1)^1]++;
v[(re&1)^1].pb(i+1);
}
}
// tep.pb(0);
// tep.pb(i);
// ll re=use_machine(tep);
// cnt[re]++;
// ans[re]++;
// v[re].pb(i);
}
// for(ll i=0;i<2;i++){
// cout<<"i: "<<i<<'\n';
// for(auto &it:v[i]){
// cout<<it<<' ';
// }
// cout<<'\n';
// }
if(2*B+1>=n){
return cnt[0];
}
if(cnt[0]>=cnt[1]){
ll pt=2*B+1;
while(pt<n){
vll tep;
ll cur=0;
for(ll rep=0;rep<cnt[0];rep++){
tep.pb(v[0][rep]);
if(pt<n){
tep.pb(pt);
pt++;
cur++;
}
}
ll re=use_machine(tep);
ll tep2=(re+1)/2;
ans[1]+=tep2;
ans[0]+=cur-tep2;
}
return ans[0];
}
else{
ll pt=2*B+1;
while(pt<n){
vll tep;
ll cur=0;
for(ll rep=0;rep<cnt[1];rep++){
tep.pb(v[1][rep]);
if(pt<n){
tep.pb(pt);
pt++;
cur++;
}
}
ll re=use_machine(tep);
ll tep2=(re+1)/2;
ans[0]+=tep2;
ans[1]+=cur-tep2;
}
return ans[0];
}
}
