#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;
mt19937 rnd(1488);
int rnd_(int n)
{
int x = rnd();
x = abs(x);
x %= n;
return x;
}
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;
}
random_shuffle(ind.begin() + 1, ind.end() , rnd_);
vector <int> a;
vector <int> b;
a.push_back(0);
int sq = sqrt(n);
sq = 99;
int ind_ = -1;
for (int i = 1; i < n; i++) {
if ((a.size() >= 3) and (i + 1 < n))
{
int i1 = ind[i];
int i2 = ind[i + 1];
int x = use_machine({ a[0] , i1 , a[1] , i2 , a[2] });
if (x == 0)
{
a.push_back(i1);
a.push_back(i2);
}
if (x == 4)
{
b.push_back(i1);
b.push_back(i2);
}
if (x == 2)
{
if (use_machine({ 0 , i1 }) == 0)
{
a.push_back(i1);
b.push_back(i2);
}
else
{
a.push_back(i2);
b.push_back(i1);
}
}
i++;
}
else
{
if ((b.size() >= 3) and (i + 1 < n))
{
int i1 = ind[i];
int i2 = ind[i + 1];
int x = use_machine({ b[0] , i1 , b[1] , i2 , b[2] });
if (x == 0)
{
b.push_back(i1);
b.push_back(i2);
}
if (x == 4)
{
a.push_back(i1);
a.push_back(i2);
}
if (x == 2)
{
if (use_machine({ 0 , i1 }) == 0)
{
a.push_back(i1);
b.push_back(i2);
}
else
{
a.push_back(i2);
b.push_back(i1);
}
}
i++;
}
else
{
if (use_machine({ 0 , ind[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() >= a.size()) {
f = 1;
swap(a, b);
}
vector <int> u;
for (int i = ind_; i < n; i++) {
u.push_back(ind[i]);
if ((u.size() == a.size() - 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;
}
