#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int block = 130;
int init(vector<int> &a, vector<int> &b) {
a.pb(0);
vector<int> v = {0, 1};
if(use_machine(v)) {
b.pb(1);
} else {
a.pb(1);
}
v = {0, 2};
if(use_machine(v)) {
b.pb(2);
} else {
a.pb(2);
}
return 3;
}
int count_mushrooms(int n) {
if(n == 2) {
vector<int> v = {0, 1};
return 2 - use_machine(v);
}
vector<int> a;
vector<int> b;
int idx = init(a, b);
for(int i = 0; i < min(block, n / 2); i++) {
if(idx == n) {
break;
}
if(idx == n - 1) {
vector<int> v = {0, idx};
if(use_machine(v)) {
b.pb(idx);
} else {
a.pb(idx);
}
idx++;
break;
}
vector<int> v;
if((int) a.size() >= 2) {
v = {a[0], idx, a[1], idx + 1};
int tmp = use_machine(v);
if(tmp & 2) {
b.pb(idx);
} else {
a.pb(idx);
}
if(tmp & 1) {
b.pb(idx + 1);
} else {
a.pb(idx + 1);
}
} else {
v = {b[0], idx, b[1], idx + 1};
int tmp = use_machine(v);
if(tmp & 2) {
a.pb(idx);
} else {
b.pb(idx);
}
if(tmp & 1) {
a.pb(idx + 1);
} else {
b.pb(idx + 1);
}
}
idx += 2;
}
int ans = 0;
while(idx < n) {
bool use_b = false;
int l = a.size();
if(b.size() > a.size()) {
use_b = true;
l = b.size();
}
l = min(l, n - idx);
int cnt = 0;
vector<int> v;
while(cnt < l) {
if(use_b) {
v.pb(b[cnt]);
} else {
v.pb(a[cnt]);
}
v.pb(idx);
idx++;
cnt++;
}
int tmp = use_machine(v);
if(!use_b) {
ans += l - (tmp / 2 + tmp % 2);
if(tmp % 2) {
b.pb(idx - 1);
} else {
a.pb(idx - 1);
ans--;
}
} else {
ans += (tmp / 2 + tmp % 2);
if(tmp % 2) {
a.pb(idx - 1);
ans--;
} else {
b.pb(idx - 1);
}
}
}
return ans + (int) a.size();
}
