#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 20010;
const int sqr = 123;
int mark[N];
int count_mushrooms(int n) {
vector <int> A, B;
A.push_back(0);
vector <int> aux;
for(int i = 0;i < n;i++){
aux.push_back(i);
}
int tt = use_machine(aux);
if(tt == 1){
int x = use_machine({0, 1});
if(x == 1){
return 1;
}
A.push_back(1);
}
else if(tt == 0){
return n;
}
else{
int l = 1, r = n-1;
int ans = 0;
while(l <= r){
int mid = (l+r)/2;
aux.clear();
for(int i = 0;i <= mid;i++){
aux.push_back(i);
}
tt = use_machine(aux);
if(tt < 2){
l = mid+1;
}
else if(tt > 2){
r = mid-1;
}
else{
ans = mid;
break;
}
}
A.push_back(ans);
}
for(auto x :A)
mark[x] = 1;
vector <int> valores;
for(int i = 0;i < n;i++){
if(!mark[i]) valores.push_back(i);
}
int cnt = 0;
for(int i = 0;i < min((int)valores.size(), 2*(((int)valores.size()+sqr-1)/sqr+1));i += 2){
if(i+1 == min((int)valores.size(), 2*(((int)valores.size()+sqr-1)/sqr+1))){
int t = use_machine({0, valores[i]});
if(t == 1) B.push_back(valores[i]);
else A.push_back(valores[i]);
cnt++;
}
else{
//cout << valores[i] << ' ' << A[1] << ' ' << valores[i+1] << endl;
int t = use_machine({0, valores[i], A[1], valores[i+1]});
if(t == 0){
A.push_back(valores[i]);
A.push_back(valores[i+1]);
}
else if(t == 1){
A.push_back(valores[i]);
B.push_back(valores[i+1]);
}
else if(t == 2){
B.push_back(valores[i]);
A.push_back(valores[i+1]);
}
else{
B.push_back(valores[i]);
B.push_back(valores[i+1]);
}
cnt += 2;
}
}
if(cnt == (int)valores.size()) return A.size();
int st = valores[cnt];
int typ = (A.size() >= B.size() ? 0 : 1);
int res = A.size();
for(int i = cnt;i < min((int)valores.size(), st+sqr);i++){
vector <int> query;
int x = i;
int con = 0;
while(x < (int)valores.size()){
query.push_back((typ == 0 ? A[(x-st)/(sqr)] : B[(x-st)/(sqr)]));
query.push_back(valores[x]);
con += 2;
x += sqr;
}
query.push_back((typ == 0 ? A.back() : B.back()));
/*for(auto x : query){
cout << x << ' ';
}*/
//cout << endl;
res += (typ == 0 ? (con-use_machine(query))/2 : use_machine(query)/2);
}
return res;
}
