#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 11;
bool a[N];
bool X[N];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
/*int use_machine(vector<int> x) {
int c = 0;
for (int i = 1; i < (int)x.size(); i++) {
if (X[x[i]] != X[x[i - 1]]) c++;
}
return c;
}*/
int count_mushrooms(int n) {
if (n <= 220) {
int ans = 1;
for (int j = 1; j < n; j++) {
if (use_machine({ 0, j }) == 0) {
ans++;
}
}
return ans;
}
else {
vector<int> inds(n);
for (int i = 0; i < n; i++) {
inds[i] = i;
}
shuffle(inds.begin() + 1, inds.end(), rng);
int block = sqrtl(n / 81);
vector <int> a, b;
a = { 0 };
int last = 0;
for (int j = 1; j <= 2 * block - 1; j++) {
if (use_machine({ 0, inds[j] }) == 1) b.push_back(inds[j]);
else a.push_back(inds[j]);
last = j;
if ((int)a.size() == block || (int)b.size() == block) break;
}
int ans = (int)a.size();
block = max((int)a.size(), (int)b.size());
if ((int)a.size() < (int)b.size()) {
for (int j = last + 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(inds[j + l]);
}
int q = use_machine(cur);
if (q % 2 == 0) {
b.push_back(cur.back());
block++;
j--;
}
ans += ((q + 1) / 2);
}
}
else {
for (int j = last + 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(inds[j + l]);
}
int q = use_machine(cur);
if (q % 2 == 0) {
a.push_back(cur.back());
block++;
j--;
}
ans += (sz - ((q + 1) / 2));
}
}
return ans;
}
}
/*
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> X[i];
}
cout << count_mushrooms(n) << "\n";
for (int c = 1; c <= 100; c++) {
cout << count_mushrooms(n) << "\n";
}
}
*/
