#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
if (n < 200) {
int ans=1;
for(int i=1;i<n;i++) {
vector<int> qry;
qry = {0,i};
int res = use_machine(qry);
if(res==0) ans++;
}
return ans;
}
else {
vector<int> qry;
vector<int> a, b;
a.push_back(0);
qry = {0,1};
int res= use_machine(qry);
if(res==1) b.push_back(1);
else a.push_back(1);
qry = {0,2};
res= use_machine(qry);
if(res==1) b.push_back(2);
else a.push_back(2);
int k = 2*sqrt(n);
int cur=3;
if(a.size()>=2) {
while(cur<k) {
qry = {a[0],cur,a[1],cur+1};
int res = use_machine(qry);
if(res==0) {
a.push_back(cur);
a.push_back(cur+1);
}
if(res==1) {
a.push_back(cur);
b.push_back(cur+1);
}
if(res==2) {
a.push_back(cur+1);
b.push_back(cur);
}
if(res==3) {
b.push_back(cur);
b.push_back(cur+1);
}
cur+=2;
}
}
else {
while(cur<k) {
qry = {b[0],cur,b[1],cur+1};
int res = use_machine(qry);
if(res==0) {
b.push_back(cur);
b.push_back(cur+1);
}
if(res==1) {
b.push_back(cur);
a.push_back(cur+1);
}
if(res==2) {
b.push_back(cur+1);
a.push_back(cur);
}
if(res==3) {
a.push_back(cur);
a.push_back(cur+1);
}
cur+=2;
}
}
bool swapped = false;
if(a.size()<b.size()) {
swapped=true;
swap(a,b);
}
qry = {};
int i=0;
int ans=0;
while(cur<n) {
qry.push_back(a[i]);
if(i<(int)a.size()-1) {
qry.push_back(cur);
i++;
cur++;
}
else {
int res = use_machine(qry);
ans += res/2;
qry = {};
i=0;
}
}
if(qry.size()>0) {
qry.push_back(a[i]);
res = use_machine(qry);
ans += res/2;
}
//cout<<"a: "<<a.size()<<"\n";
//cout<<"b: "<<b.size()<<"\n";
if(!swapped) return n - b.size() - ans;
else return b.size() + ans;
}
return 0;
}
