#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 11;
int count_mushrooms(int n) {
if (n <= 10) {
int ans = 1;
for (int j = 1; j < n; j++) {
if (use_machine({ 0, j }) == 0) {
ans++;
}
}
return ans;
}
else {
int block = sqrtl(n);
vector <int> a, b;
a = { 0 };
for (int j = 1; j <= 2 * block; j++) {
if (use_machine({ 1, j }) == 1) b.push_back(j);
else a.push_back(j);
}
int ans = (int)a.size();
if ((int)a.size() < (int)b.size()) {
for (int j = 2 * block + 1; j < n; j += block) {
vector <int> cur = {};
for (int l = 0; l < min(n - j, block); l++) {
cur.push_back(b[l]);
cur.push_back(j + l);
}
cur.push_back(b[block]);
ans += (use_machine(cur) / 2);
}
}
else {
for (int j = 2 * block + 1; j < n; j += block) {
vector <int> cur = {};
int sz = 0;
for (int l = 0; l < min(n - j, block); l++) {
sz++;
cur.push_back(a[l]);
cur.push_back(j + l);
}
cur.push_back(a[block]);
ans += (sz - (use_machine(cur) / 2));
}
}
return ans;
}
}
