#include "mushrooms.h"
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
namespace{
const int K = 90;
}
int count_mushrooms(int n) {
int ans = 1;
vector<int> a, b;
a.push_back(0);
int cur = 1;
vector<int> askf = {0, 1};
if(use_machine(askf) == 1){
b.push_back(1);
}
else{
ans++;
a.push_back(1);
}
if(n == 2) return ans;
if((int)a.size() < 2){
askf = {0, 2};
if(use_machine(askf) == 1){
b.push_back(2);
}
else{
ans++;
a.push_back(2);
}
}
cur = 3;
while(cur + 1 < min(n, 2 * K)){
int sa = (int)a.size(), sb = (int)b.size();
if(sa >= 2){
askf = {a[0], cur, a[1], cur + 1};
int res = use_machine(askf);
if(res & 1){
b.push_back(cur + 1);
}
else{
a.push_back(cur + 1);
}
if(res >= 2){
b.push_back(cur);
}
else{
a.push_back(cur);
}
}
else{
askf = {b[0], cur, b[1], cur + 1};
int res = use_machine(askf);
if(res & 1){
a.push_back(cur + 1);
}
else{
b.push_back(cur + 1);
}
if(res >= 2){
a.push_back(cur);
}
else{
b.push_back(cur);
}
}
cur += 2;
}
while(cur < n){
int sa = (int)a.size(), sb = (int)b.size();
if(sa >= sb){
vector<int> ask;
int ina = 0, imp = cur;
for(int i = 0; i < sa; i++){
if(cur == n) break;
ask.push_back(cur);
ask.push_back(a[i]);
cur++;
if(i > 0) ina++;
}
int res = use_machine(ask);
if(res & 1){
b.push_back(imp);
}
else{
a.push_back(imp);
ans++;
}
ans += ina - res / 2;
}
else{
vector<int> ask;
int imp = cur;
for(int i = 0; i < sb; i++){
if(cur == n) break;
ask.push_back(cur);
ask.push_back(b[i]);
cur++;
}
int res = use_machine(ask);
if(res & 1){
a.push_back(imp);
ans++;
}
else b.push_back(imp);
ans += res / 2;
}
}
return ans;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run -g mushrooms.cpp stub.cpp
