#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(s) ((int)s.size())
const int inf = 1e9;
void print(vector<int> &a) {
for (int v: a) cout << v << ' ';
cout << '\n';
}
int count_mushrooms(int n) {
if (n < 10) {
int s = 1;
for (int i = 0; i < n-1; i++) s += 1-use_machine(vector<int>({0, i+1}));
return s;
}
int bst = inf;
int num_it = -1;
for (int i = 0; i < n; i++) { // how many iterations to go through before starting main seq
int steps = i+2;
int found = 3+2*i;
int num_processed = 3+2*i;
while (found < n) {
steps++;
found += (1+num_processed)/2;
num_processed++;
}
if (steps < bst) {
bst = steps;
num_it = i;
}
}
vector<int> tp[2];
tp[0].push_back(0);
int cutoff = num_it + 2;
int l = 1;
for (; l < n && max(sz(tp[0]), sz(tp[1])) < cutoff; ) {
// print(tp[0]);
// print(tp[1]);
vector<int> m;
bool x = sz(tp[1])>sz(tp[0]);
int csz = sz(tp[x]);
m.push_back(tp[x][0]);
m.push_back(l++);
if (csz > 1) {
m.push_back(tp[x][1]);
m.push_back(l++);
}
int v = use_machine(m);
tp[x^(v&1)].push_back(l-1);
if (csz > 1) {
tp[x^((v/2)&1)].push_back(l-2);
}
}
// print(tp[0]);
// print(tp[1]);
int s = 0;
while (l < n) {
bool x = sz(tp[1])>sz(tp[0]);
vector<int> m;
int num_processed = min(sz(tp[x]), n-l);
for (int i: tp[x]) {
m.push_back(i);
if (l < n) m.push_back(l++);
}
int v = use_machine(m);
int num_bs = (v+(v&1))/2;
s += x ? num_bs : (num_processed-num_bs);
if (l < n) {
tp[(v&1)^x].push_back(l-1);
s -= (v&1)^x^1;
}
}
// print(tp[0]);
// print(tp[1]);
return s + sz(tp[0]);
}
