#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
vector<int> ans (n);
vector<int> marc (n);
marc[0] = 1;
ans[0] = 1;
vector<int> ask;
for(int i = 0; i < n; i++)
ask.push_back(i);
int val = use_machine(ask);
marc[n - 1] = 1;
ans[n - 1] = val % 2 == 0;
int a = 0;
if(val == 0) return n;
else if(val == 1){
ask.clear();
ask.push_back(0);
ask.push_back(1);
if(use_machine(ask) == 1) return 1;
a = 1;
}
else if(val % 2 == 0) a = n - 1;
else{
int ini = 1, fim = n - 1;
while(ini != fim){
int mid = (ini + fim) >> 1;
ask.clear();
ask.push_back(0);
for(int i = ini; i <= mid; i++)
ask.push_back(i);
int aux = use_machine(ask);
marc[mid] = 1;
ans[mid] = aux % 2 == 0;
if(aux % 2 == 0){
a = mid;
break;
}
if(aux == val) fim = mid - 1;
else ini = mid + 1, val -= aux;
}
if(a == 0) return 1;
}
queue<int> fila;
for(int i = 0; i < n; i++){
if(marc[i]) continue;
fila.push(i);
}
while(fila.size() > 1){
int c = fila.front();
fila.pop();
int d = fila.front();
fila.pop();
vector<int> ask2 (4);
ask2[0] = 0;
ask2[1] = c;
ask2[2] = a;
ask2[3] = d;
int aux = use_machine(ask2);
if(aux == 0){
ans[c] = 1;
ans[d] = 1;
}
else if(aux == 1){
ans[c] = 1;
ans[d] = 0;
}
else if(aux == 2){
ans[c] = 0;
ans[d] = 1;
}
else if(aux == 3){
ans[c] = 0;
ans[d] = 0;
}
}
if(!fila.empty()){
int c = fila.front();
fila.pop();
vector<int> ask2 (2);
ask2[0] = 0;
ask2[1] = c;
int aux = use_machine(ask2);
if(aux == 0) ans[c] = 1;
if(aux == 1) ans[c] = 0;
}
int ret = 0;
for(int i = 0; i < n; i++)
ret += ans[i];
return ret;
}
