#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int B = 32;
mt19937 rng(9679 + time(nullptr) + chrono::steady_clock::now().time_since_epoch().count() + (uint64_t) new char);
vector<int> v;
int solve(int l, int r) {
int sz = r-l+1;
shuffle(v.begin()+l, v.begin()+r+1, rng);
vector<int> a;
a.push_back(0);
for (int i = l; i <= r; i++) {
a.push_back(v[i]);
}
int x = use_machine(a);
if (!x) return sz;
else if (x == sz) {
return sz/2;
}
else {
int mid = (l+r)/2;
// int mid = rng() % (r-l) + l;
return solve(l, mid) + solve(mid+1, r);
}
}
int count_mushrooms(int n) {
v.resize(n);
for (int i = 0; i < n; i++) v[i] = i;
int ans = 1;
for (int i = 1; i < n; i+=B) {
ans += solve(i, min(n-1, i+B-1));
}
return ans;
}
/*
bloques de tamaño x
solve(l, r) -> shuffleo + partir por la mitad o partir random o en sqrt hijos
*/
