#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{0};
vector<int> B;
int i = 1;
for (; i < n; i++){
int type = use_machine({i-1,i});
if(type == 1){
lastType = 1-lastType;
}
if(lastType == 0) A.push_back(i);
else B.push_back(i);
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)+1)/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;
}
