#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 cal(vector<int>&v, int st, int n) {
set<int> s;
for(auto x : v) s.insert(x);
int ans=v.size();
// for(auto x : a) cout << x << ' ';
// cout << endl;
for(int i=st; i<n; i++) {
vector<int> cur;
int idx=0;
while(idx < v.size() && i < n) {
if(s.count(i)) {
i++; continue;
}
cur.push_back(v[idx]);
cur.push_back(i);
idx++; i++;
}
if(cur.size() == 1) continue;
int val=use_machine(cur);
if(val%2 == 0) ans++;
// for(auto x : cur) cout << x << ' ';
// cout << endl;
ans+=(cur.size()-1-val)/2;
i--;
}
return ans;
}
int count_mushrooms(int n) {
vector<int> a={0}, 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 lo=2*sqrt(n);
for(int i=1; i<lo; i++) {
if(use_machine({0, i}) == 1) b.push_back(i);
else a.push_back(i);
if(a.size() >= sqrt(n) || b.size() > sqrt(n)) {
lo=i+1; break;
}
}
int ans=0;
if(a.size() >= sqrt(n)) ans = cal(a, lo, n);
else ans=n-cal(b, lo, n);
return ans;
}
