#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
// A:0,B:1
int count_mushrooms(int n) {
int lastType = 0;
int BlockSize = 100;
vector<int> A{1};
vector<int> B;
int i = 0;
for (; i+1 < n; i++){
int type = use_machine({i,i+1});
if(type == 1){
lastType = 1-lastType;
}
if(lastType == 0) A.push_back(i+1);
else B.push_back(i+1);
if(A.size() > BlockSize || B.size() > BlockSize) break;
}
auto merge_ask = [&](vector<int> unknown,vector<int> same){
vector<int> qry;
for(int j = 0;j < unknown.size();j++){
qry.push_back(same[j]);
qry.push_back(unknown[j]);
}
qry.push_back(same[unknown.size()]);
return use_machine(qry)/2;
};
int tot = A.size();
i++;
vector<int> cur;
for(;i < n;i++){
if(cur.size() == BlockSize){
if(A.size() > B.size()){
int diff = merge_ask(cur,A);
tot += cur.size()-diff;
}else{
int diff = merge_ask(cur,B);
tot += diff;
}
cur.clear();
}
cur.push_back(i);
}
if(cur.empty()) return tot;
if(A.size() > B.size()){
int diff = merge_ask(cur,A);
tot += cur.size()-diff;
}else{
int diff = merge_ask(cur,B);
tot += diff;
}
return tot;
}
