#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
vector<int> state;
int cmm = 0;
int flip(int k){
if (k==2) return 1;
return 2;
}
pii check(int i, int j){
cmm++;
if(state[0]==state[1] && state[1]==state[2]){
int x = use_machine({0, i, 1, 2, j});
if(state[0]==1)return {((x&2)>>1)+1, (x&1)+1};
else return {flip(((x&2)>>1)+1), flip((x&1)+1)};
}
if(state[0]==state[1]){
int x = use_machine({0, i, 1, 2, j})-1;
if(state[0]==1)return {((x&2)>>1)+1, flip((x&1)+1)};
else return {flip(((x&2)>>1)+1), (x&1)+1};
}
if(state[1]==state[2]){
int x = use_machine({1, i, 2, 0, j})-1;
//cout << x << '\n';
//cout << 1 << ' ' << i << ' '<< 2 << ' ' << 0 << ' ' << j << '\n';
if(state[1]==1)return {((x&2)>>1)+1, flip((x&1)+1)};
else return {flip(((x&2)>>1)+1), (x&1)+1};
}
if(state[0]==state[2]){
int x = use_machine({0, i, 2, 1, j})-1;
if(state[0]==1)return {((x&2)>>1)+1, flip((x&1)+1)};
else return {flip(((x&2)>>1)+1), (x&1)+1};
}
}
pii test(vector<int> tester, vector<int> tested, int tri){
vector<int> cun;
for(int i = 0;i<tester.size();i++){
cun.push_back(tester[i]);
cun.push_back(tested[i]);
}
cmm++;
auto x = use_machine(cun);
int cn=(x/2)+(x&1);
if(tri==1)cn=tester.size()-cn;
int la=tri;
if(x&1)la=flip(la);
return {cn, la};
}
const int cut=170;
int count_mushrooms(int n) {
state.assign(n, 0);
//0 not known 1 A 2 B
state[0]=1;
int second = use_machine({0, 1})+1;
state[1]=second;
if(n==2)return 1+((second-1)^1);
int third = use_machine({0, 2})+1;
cmm+=2;
state[2]=third;
if (n<=448){
int res = 1+(second==1 ? 1:0) + (third==1 ? 1:0);
//cout << "res: " << res << '\n';
if (!(n&1))res+=use_machine({0, n-1})^1;
cmm++;
for(int test=4;test<n;test+=2){
auto x = check(test-1, test);
cmm++;
//cout << x.first << ' ' << x.second << '\n';
if(x.first==1)res++;
if(x.second==1)res++;
}
return res;
}
for(int tes=4;tes<cut;tes+=2){
auto x = check(tes-1, tes);
cmm++;
state[tes-1]=x.first;
state[tes]=x.second;
}
vector<int> as, bs, uki;
int res = 0;
for(int i =0;i<n;i++){
if (state[i]==1){
as.push_back(i);
res++;
}
else if (state[i]==2) bs.push_back(i);
else uki.push_back(i);
}
int ntt=1;
if (as.size()<bs.size()){
swap(as, bs);
ntt=2;
}
while(uki.size()!=0){
if (uki.size()>=as.size()){
vector<int> tes;
for(int i = 0;i<as.size();i++){
tes.push_back(uki.back());
uki.pop_back();
}
auto xx = test(as, tes, ntt);
res+=xx.first;
if(xx.second==ntt)as.push_back(tes.back());
else {
bs.push_back(tes.back());
if(bs.size()>as.size()){
ntt=flip(ntt);
swap(as, bs);
}
}
cmm++;
}
else{
while(uki.size()<as.size()){
as.pop_back();
}
res+=test(as, uki, ntt).first;
cmm++;
break;
}
}
return res;
}
