#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int n)
{
int ans = 0, type = 0;
int BLOCK_SIZE = sqrt(n);
for (int i = 0; i < n; ++i)
{
vector<int> curr;
int bound = min(n, i + BLOCK_SIZE - 1);
for (int j = i; j <= bound; ++j)
{
curr.push_back(j);
}
if (use_machine(curr) == 0)
{
if (type == 0) ans += BLOCK_SIZE;
i = bound;
continue;
}
int l = i + 1;
int r = bound;
while (l <= r)
{
int mid = (l + r) / 2;
vector<int> query;
for (int j = i; j <= mid; ++j)
{
query.push_back(j);
}
int result = use_machine(query);
if (result == 0)
{
l = mid + 1;
}
else
{
r = mid - 1;
}
}
if (type == 0) ans += (r - i + 1);
i = r;
type = 1 - type;
}
return ans;
}
