#include <iostream>
#include "mushrooms.h"
using namespace std;
bool debug=0;
#define dout if(debug)cout
#define pb push_back
#define mp make_pair
int count_mushrooms(int n) {
vector<int> m = {0};
if(n<200){
int smallans=1;
for(int i=1; i<n; i++){
m = {0, i};
smallans += (1-use_machine(m));
}
return smallans;
}
int answer;
int cnt0=1, cnt1=0;
vector<int> ones, zeros={0};
vector<bool> known(n+2, 0);
known[0]=1;
int val;
pair<int, int> zs;
// spend 2 queries finding atleast a 2nd instance of 1, or 2 instances of 0:
known[1]=1;
bool usingzeros;
m={0,1};
if(use_machine(m)){
// {0,1}
cnt1++;
ones.pb(1);
known[2]=1;
m={0,2};
if(use_machine(m)){
// {0,1,1}
cnt1++;
ones.pb(2);
zs = mp(1,2);
usingzeros = false;
} else{
// {0,1,0}
cnt0++;
zeros.pb(2);
zs = mp(0,2);
usingzeros = true;
}
} else{
cnt0++;
zeros.pb(1);
zs = mp(0,1);
usingzeros = true;
}
// querying {1,x,1,y} tells us all about x and y.
// doing this 100 times is pretty nice
dout<<"finished the first 2 queries. we have the pair ("<<zs.first<<","<<zs.second<<").\n";
int a=1,b=1;
for(int j=0; j<min(98, n/3); j++){
while(known[a]) a++;
known[a]=1;
while(known[b]) b++;
known[b]=1;
m={zs.first, a, zs.second, b};
val = use_machine(m);
if(val==0){
// ns[a]=ns[b]=zs
if(usingzeros){
cnt0+=2;
zeros.pb(a);
zeros.pb(b);
} else{
cnt1+=2;
ones.pb(a);
ones.pb(b);
}
} else if(val==1){
cnt0++;
cnt1++;
if(usingzeros){
ones.pb(a);
zeros.pb(b);
} else{
ones.pb(b);
zeros.pb(a);
}
} else if(val==2){
// a is the same as usingzeros
cnt0++;
cnt1++;
if(usingzeros){
zeros.pb(a);
ones.pb(b);
} else{
ones.pb(a);
zeros.pb(b);
}
} else{
// a==b==!zs
if(usingzeros){
cnt1+=2;
ones.pb(a);
ones.pb(b);
} else{
cnt0+=2;
zeros.pb(a);
zeros.pb(b);
}
}
}
if(debug)
{
cout<<"$ known: ";
for(int i=0; i<n; i++){
cout<<known[i]<<" ";
}cout<<"\n";
}
int next_unknown = 1;
while(known[next_unknown])next_unknown++;
if(cnt0 >= cnt1){
answer = n-cnt1;
while(next_unknown < n){
m.resize(0);
for(int i=0; i<cnt0; i++){
if(next_unknown >= n)break;
m.pb(next_unknown);
m.pb(zeros[i]);
known[next_unknown]=true;
while(known[next_unknown])next_unknown++;
}
answer -= (use_machine(m)+1)/2;
}
return answer;
} else{
answer = cnt0;
while(next_unknown < n){
m.resize(0);
for(int i=0; i<cnt1; i++){
if(next_unknown >= n)break;
m.pb(next_unknown);
m.pb(ones[i]);
known[next_unknown]=true;
while(known[next_unknown])next_unknown++;
}
answer += (use_machine(m)+1)/2;
}
return answer;
}
}
