#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
vector<int> A = {0};
vector<int> B;
int b = 100;
int i = 1;
while(A.size() < b && B.size() < b){
if(i == n) return A.size();
if(use_machine({0,i}) == 0) A.push_back(i);
else B.push_back(i);
}
bool swapped = false;
if(B.size() == b){
swapped = true;
swap(A,B);
}
int count = 0;
while(i < n){
int qs = min(b,n-i);
vector<int> arr;
for(int j = 0; j< qs; j++){
arr.push_back(A[j]);
arr.push_back(i+j);
}
count += qs-(use_machine(arr)+1)/2;
i += qs;
}
count += A.size();
if(swapped) count = n - count;
return count;
}
