#include "mushrooms.h"
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
int count_mushrooms(int n) {
set<int> v, a;
int q = 2*sqrt(n);
a.insert(0);
if(n<=225){
int o = 1;
for(int i=1; i<n; i++){
o++;
o-=use_machine({0, i});
}
return o;
}
//first part setup
int first = use_machine({1, 0, 2});
int touse, tovis =0;
bool flag= true;
if(first ==0){// AAA
touse = 1;
a.insert(1);
a.insert(2);
}
else if(first==2) {//BAB
touse=1; tovis = 2;
v.insert(1);
v.insert(2);
flag = false;//so if usig B
}
else{
first = use_machine({1, 0});
// {1, 0, 2} givees 1
// [1, 0] gives 1
if(first==1){// a[1]= B
touse = 2;
a.insert(2);
v.insert(1);
}
else{// a[1]=A
touse = 1;
a.insert(1);
v.insert(2);
}
}
// 2 part: fid the first q
// we have positio of 0, 1, 2
for(int i=3; i<q-1; i+=2){
int x = use_machine({touse, i, tovis, i+1});
if(flag){// aka if A
if(x==0) {// AAAA
a.insert(i+1);
a.insert(i);
}
if(x==1){ //AAAB
a.insert(i);
v.insert(i+1);
}
if(x==2){// ABAA
a.insert(i+1);
v.insert(i);
}
if(x==3){// ABAB
v.insert(i+1);
v.insert(i);
}
}
else{// if B
if(x==0) {// AAAA
v.insert(i+1);
v.insert(i);
}
if(x==1){ //AAAB
v.insert(i);
a.insert(i+1);
}
if(x==2){// ABAA
v.insert(i+1);
a.insert(i);
}
if(x==3){// ABAB
a.insert(i+1);
a.insert(i);
}
}
}
// third part do the rest
// queryig q etters at the same time
int vv = v.size(), aa = a.size();
flag = (vv<=aa);
int fac = max(vv, aa);
int vaa = q;
for(int i=q; i<n&& i+fac<n; i+=fac){
vector<int> mm;
if(flag){// usig As
int vo = 0;
for(auto it: a){
mm.push_back(it);
mm.push_back(vo+i);
vo++;
}
int vi = use_machine(mm);
aa+=(fac-(vi+1)/2);
}
else{
int vo = 0;
for(auto it: v){
mm.push_back(it);
mm.push_back(vo+i);
vo++;
}
int vi = use_machine(mm);
aa+=(vi+1)/2;
}
vaa = i;
}
if(vaa<n){
vector<int> mm;
if(flag){// usig As
int vo = 0;
for(auto it: a){
if(vo+vaa>=n)break;
mm.push_back(it);
mm.push_back(vo+vaa);
vo++;
}
int vi = use_machine(mm);
aa+=(fac-(vi+1)/2);
}
else{
int vo = 0;
for(auto it: v){
if(vo+vaa>=n)break;
mm.push_back(it);
mm.push_back(vo+vaa);
vo++;
}
int vi = use_machine(mm);
aa+=(vi+1)/2;
}
}
return aa;
}
