#include <bits/stdc++.h>
#define l int
using namespace std;
#include "mushrooms.h"
vector<l> positions;
vector<l> cocaine;
vector<l> flour;
l threshold = 140;
l uses = 0;
l machine(vector<l> a) {
uses++;
return use_machine(a);
}
void psh(vector<l>* a, vector<l> b) {
a->insert(a->end(), b.begin(), b.end());
}
void psh_unequal(vector<l>* fs, vector<l>* sec, vector<l> elements) {
for (int i = 0; i < elements.size(); i++) {
if (i&1) sec->push_back(elements[i]);
else fs->push_back(elements[i]);
}
}
pair<vector<l>*, vector<l>*> return_bigger() {
if (cocaine.size() > flour.size()) return {&cocaine, &flour};
else return {&flour, &cocaine};
}
pair<vector<l>*, vector<l>*> get_two() {
l result;
while (cocaine.size() < 2 && flour.size() < 2) {
result = machine({0, positions.back()});
if (result == 0) cocaine.push_back(positions.back());
else flour.push_back(positions.back());
positions.pop_back();
}
return return_bigger();
}
pair<vector<l>*, vector<l>*> get_amount_by_two(l n) {
auto [same, different] = get_two();
l a, b, result;
while (positions.size() > 1 && cocaine.size() < n && flour.size() < n) {
a = positions.back(); positions.pop_back();
b = positions.back(); positions.pop_back();
result = machine({(*same)[0], a, (*same)[1], b});
if (result == 0) {
same->insert(same->end(), {a, b});
} else if (result == 1) {
same->push_back(a);
different->push_back(b);
} else if (result == 2) {
same->push_back(b);
different->push_back(a);
} else {
different->insert(different->end(), {a, b});
}
}
if (cocaine.size() < n && flour.size() < n && positions.size() == 1) {
result = machine({0, positions.back()});
if (result == 0) cocaine.push_back(positions.back());
else flour.push_back(positions.back());
positions.pop_back();
}
return return_bigger();
}
pair<vector<l>*, vector<l>*> get_amount(l n, vector<l>* same, vector<l>* different) {
l a, b, c, d, result;
vector<vector<l>> unequal;
while (positions.size() > 2 && cocaine.size() < n && flour.size() < n) {
a = positions.back(); positions.pop_back();
b = positions.back(); positions.pop_back();
c = positions.back(); positions.pop_back();
result = machine({(*same)[0], a, (*same)[1], b, (*same)[2], c});
if (result == 0) {
psh(same, {a, b, c});
} else if (result == 1) {
psh(same, {a, b});
psh(different, {c});
} else if (result == 4) {
psh(same, {c});
psh(different, {a, b});
} else if (result == 5) {
psh(different, {a, b, c});
} else {
if (result == 2) psh(same, {c});
else psh(different, {c});
unequal.push_back({a, b});
n--;
}
}
if (cocaine.size() < n && flour.size() < n && !positions.empty()) {
get_amount_by_two(n);
}
vector<l> x, y, z;
while (unequal.size() > 2) {
x = unequal.back(); unequal.pop_back();
y = unequal.back(); unequal.pop_back();
z = unequal.back(); unequal.pop_back();
result = machine({(*same)[0], x[0], (*same)[1], y[0], (*same)[2], z[0]});
if (result == 0) {
psh_unequal(same, different, x);
psh_unequal(same, different, y);
psh_unequal(same, different, z);
} else if (result == 1) {
psh_unequal(same, different, x);
psh_unequal(same, different, y);
psh_unequal(different, same, z);
} else if (result == 4) {
psh_unequal(different, same, x);
psh_unequal(different, same, y);
psh_unequal(same, different, z);
} else if (result == 5) {
psh_unequal(different, same, x);
psh_unequal(different, same, y);
psh_unequal(different, same, z);
} else {
if (result == 2) psh_unequal(same, different, z);
else psh_unequal(different, same, z);
reverse(x.begin(), x.end());
x.insert(x.end(), y.begin(), y.end());
unequal.push_back(x);
}
}
if (unequal.size() == 2) {
x = unequal.back(); unequal.pop_back();
y = unequal.back(); unequal.pop_back();
result = use_machine({(*same)[0], x[0], (*same)[1], y[0]});
if (result&1) psh_unequal(different, same, y);
else psh_unequal(same, different, y);
if (result&2) psh_unequal(different, same, x);
else psh_unequal(same, different, x);
}
if (unequal.size() == 1) {
x = unequal.back(); unequal.pop_back();
result = use_machine({(*same)[0], x[0]});
if (result&1) psh_unequal(different, same, x);
else psh_unequal(same, different, x);
}
return return_bigger();
}
l count_bigger(vector<l>* same) {
l c = same->size();
l result;
vector<l> input;
while (!positions.empty()) {
input.clear();
l last;
for (int i = 0; i < same->size() && !positions.empty(); i++) {
psh(&input, {(*same)[i], positions.back()});
last = positions.back();
positions.pop_back();
}
result = machine(input);
if (result&1) {
result++;
} else {
same->push_back(last);
}
c += (input.size()/2) - (result/2);
}
return c;
}
l subtask1() {
l a, b;
while (!positions.empty()) {
a = positions.back(); positions.pop_back();
b = machine({0, a});
if (b == 0) cocaine.push_back(a);
else flour.push_back(a);
}
return cocaine.size();
}
int count_mushrooms(int n) {
cocaine.push_back(0);
for (int i = 1; i < n; i++) positions.push_back(i);
vector<l> test;
for (int i = 0; i < n; i++) test.push_back(i);
// use_machine(test);
mt19937_64 g;
g.seed(267534);
shuffle(positions.begin(), positions.end(), g);
if (n < 200) return subtask1();
auto [same, different] = get_amount_by_two(3);
assert(uses <= 3);
tie(same, different) = get_amount(threshold, same, different);
l sol = count_bigger(same);
if (*same == cocaine) return sol;
else return n - sol;
}
