#include "mushrooms.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <bitset>
using namespace std;
int count_mushrooms(int n) {
if (n <= 200) {
int col = 1;
for (int i = 1; i < n; i++) {
if (use_machine({ 0 , i }) == 0)
col++;
}
return col;
}
vector <int> ind(n);
for (int i = 0; i < n; i++) {
ind[i] = i;
}
vector <int> a;
vector <int> b;
a.push_back(0);
int sq = sqrt(n);
sq = 100;
int ind_ = -1;
for (int i = 1; i < n; i++) {
if (use_machine({ 0 , i }) == 0)
a.push_back(ind[i]);
else
b.push_back(ind[i]);
if (max(a.size(), b.size()) >= sq) {
ind_ = i + 1;
break;
}
}
bool f = 0;
int col = a.size();
if (b.size() == sq) {
f = 1;
swap(a, b);
}
vector <int> u;
for (int i = ind_; i < n; i++) {
u.push_back(ind[i]);
if ((u.size() == sq - 1) or (i == n - 1)) {
vector <int> q;
int i__ = 0;
for (int i = 0; i < u.size(); i++) {
q.push_back(a[i__]);
i__++;
q.push_back(u[i]);
}
q.push_back(a[i__]);
i__++;
int r = use_machine(q);
r /= 2;
if (f == 0)
col += u.size() - r;
else
col += r;
u.clear();
}
}
return col;
}
