#include "mushrooms.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
typedef long long llong;
const int MAXN = 100000 + 10;
const int INF = 1e9;
int min[MAXN];
int max[MAXN];
std::vector <int> order;
std::mt19937 rng(69420);
int count_mushrooms(int n)
{
for (int i = 0 ; i <= n ; ++i)
{
min[i] = n;
max[i] = 0;
}
order.resize(n);
std::iota(order.begin(), order.end(), 0);
std::shuffle(order.begin() + 1, order.end(), rng);
int ans = 0;
int ptr = 0;
int last = -1;
while (true)
{
int l = max[ptr], r = min[ptr + 1], mid;
while (l < r - 1)
{
mid = (l + r) / 2;
std::vector <int> toAsk(order.begin() + max[ptr], order.begin() + mid + 1);
int res = use_machine(toAsk);
min[ptr + res] = std::min(min[ptr + res], mid);
max[ptr + res] = std::max(max[ptr + res], mid);
if (res == 0) l = mid;
else r = mid;
}
if (ptr % 2 == 0)
{
ans += l - last;
}
assert(min[ptr + 1] == max[ptr] + 1);
if (max[ptr] == n - 1)
{
break;
}
last = l;
ptr++;
}
return ans;
}
