#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
// i = 3
// i = i+2
// i<q-1
// i q-2, or q-3
// if i ed at q-3 which meas it doest take ito case q-1 it stops f q-2
for(int i=3; i<q-1; i+=2){
int x = use_machine({touse, i, tovis, i+1}); // A?A? or V?V?
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) {// BBBB
v.insert(i+1);
v.insert(i);
}
if(x==1){ //BBBA
v.insert(i);
a.insert(i+1);
}
if(x==2){// BABB
v.insert(i+1);
a.insert(i);
}
if(x==3){// BABA
a.insert(i+1);
a.insert(i);
}
}
}
if(q%2==0){
int x = use_machine({touse, q-1});
if(flag){// usig A
if(x==1)v.insert(q-1);
else a.insert(q-1);
}
else{// usig V
if(x==1)a.insert(q-1);
else v.insert(q-1);
}
}
// rewritee the third part
int aa = a.size(), vv = v.size();
int fac = max(aa, vv);
flag = (aa>=vv);
int ast_query = q;
for(int i = q; i+fac<n; i++){
vector<int> mm;
if(flag){
int vo = 0;
for(auto it: a){
mm.push_back(vo+i);
mm.push_back(it);
vo++;
}
int query = use_machine(mm);
aa += (fac-(query+1)/2);
}
else{
int vo = 0;
for(auto it: v){
mm.push_back(vo+i);
mm.push_back(it);
vo++;
}
int query = use_machine(mm);
aa+=(query+1)/2;
}
ast_query = i;
}
// treat the rest
vector<int> mm;
if(flag){
int vo = 0;
for(auto it: a){
if(vo+ast_query>=n) break;
mm.push_back(vo+ast_query);
mm.push_back(it);
vo++;
}
int query = use_machine(mm);
aa += ((mm.size()/2) -(query+1)/2);
}
else{
int vo = 0;
for(auto it: v){
if(vo+ast_query>=n) break;
mm.push_back(vo+ast_query);
mm.push_back(it);
vo++;
}
int query = use_machine(mm);
aa+=(query+1)/2;
}
return aa;
}
