#include<bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
int firstTrue(int lo, int hi) {
hi++;
while(lo < hi) {
int mid = lo+(hi-lo)/2;
if(lo == mid) return lo+1;
vector<int> cur;
for(int i=lo; i<=mid; i++) cur.push_back(i);
int nbAdj=use_machine(cur);
if(nbAdj >= 1) hi=mid;
else if(nbAdj == hi-lo) return lo+1;
else lo=mid;
}
return lo+1;
}
int count_mushrooms(int n) {
vector<int> a, b;
int lo=0;
bool aa=true;
while(lo != n) {
int lolo=firstTrue(lo, n-1);
if(aa) for(int i=lo; i<lolo; i++) a.push_back(i);
else for(int i=lo; i<lolo; i++) b.push_back(i);
lo=lolo;
aa=!aa;
if(a.size() > sqrt(n) || b.size() > sqrt(n)) break;
}
int ans=0;
if(a.size() > sqrt(n)) {
set<int> s;
for(auto x : a) s.insert(x);
ans=a.size();
for(int i=lo; i<n; i++) {
vector<int> cur={a[0]};
int idx=1;
while(idx < a.size() && i < n) {
if(s.count(i)) {
i++; continue;
}
cur.push_back(i);
cur.push_back(a[idx]);
idx++; i++;
}
if(cur.size() == 1) continue;
ans+=(cur.size()-use_machine(cur))/2;
i--;
}
} else {
set<int> s;
for(auto x : b) s.insert(x);
ans=b.size();
for(int i=lo; i<n; i++) {
vector<int> cur={b[0]};
int idx=1;
while(idx < b.size() && i < n) {
if(s.count(i)) {
i++; continue;
}
cur.push_back(i);
cur.push_back(b[idx]);
idx++; i++;
}
if(cur.size() == 1) continue;
ans+=(cur.size()-use_machine(cur))/2;
i--;
}
ans=n-ans;
}
return ans;
}
