#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
int same(int a, int b){
vector<int> m = {a, b};
return !use_machine(m);
}
int count_mushrooms(int n) {
int q = sqrt(n);
vector<vector<int>> C(2);
C[0].push_back(0);
int leader = 0;
int i = 1;
while(i < n && max(C[0].size(), C[1].size()) < 2){
if (same(C[leader][0], i)) C[leader].push_back(i);
else C[!leader].push_back(i);
if (C[leader].size() < C[!leader].size()) leader ^=1;
i++;
}
if (i == n-1) return (int)C[0].size() + same(0, i);
while(i+1 < n && (int)max(C[0].size(), C[1].size()) <= q){
vector<int> m = {C[leader][0], i, C[leader][1], i+1};
int qry = use_machine(m);
if (qry == 0){
C[leader].push_back(i);
C[leader].push_back(i+1);
} else if (qry == 1){
C[leader].push_back(i);
C[!leader].push_back(i+1);
} else if(qry == 2){
C[!leader].push_back(i);
C[leader].push_back(i+1);
} else {
C[!leader].push_back(i);
C[!leader].push_back(i+1);
}
if (C[leader].size() < C[!leader].size()) leader ^=1;
i+=2;
}
if (i == n-1) return (int)C[0].size() + same(0, i);
int cntC = C[leader].size();
for (int j=i;j<n;j+=q){
int lim = min(q, n-j);
vector<int> m;
for (int k=0;k<lim;k++) {
m.push_back(C[leader][k]);
m.push_back(j+k);
}
m.push_back(C[leader].back());
cntC += lim - use_machine(m)/2;
}
return leader == 0 ? cntC : n - cntC;
}
