#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int SQ = 101;
int calc(vector<int> vec , int l , int r){
int ans = 0;
for(int i = l ; i < r ; i += SQ - 1){
vector<int> v = {vec[0]};
for(int j = i ; j < min(r , i + SQ) ; j++){
v.push_back(j);
v.push_back(vec[j - i + 1]);
}
ans += v.size() - 1 - use_machine(v);
}
return ans / 2;
}
int count_mushrooms(int n) {
vector<int> A = {0} , B;
int cntA = 1 , cntB = 0;
for (int i = 1 ; i < n ; i++){
vector<int> v = {0 , i};
int x = use_machine(v);
if(x == 0){
cntA++;
A.push_back(i);
}
if(x == 1){
cntB++;
B.push_back(i);
}
if(cntA >= SQ || cntB >= SQ) break;
}
if(A.size() == SQ){
cntA += calc(A , A.size() + B.size() , n);
}
if(B.size() == SQ){
cntA += n - A.size() - B.size() - calc(B , A.size() + B.size() , n);
}
return cntA;
}
