#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
std::vector<int> labels;
std::vector<std::vector<int>> lst;
int K = 110;
int ans;
void label(int p, int z) {
labels[p] = z;
lst[z].push_back(p);
if (!z) ++ans;
}
int p;
int z;
vector<int> toQ;
string subs(string s, int mask) {
for (char &c: s) if (c >= 'A' && c <= 'Z') c = (char)('0' + ((mask >> (c - 'A')) & 1));
return s;
}
int eval(const std::string &s) {
int ret = 0;
for (int i = 0; i < (int)s.size() - 1; ++i) ret += int(s[i] != s[i + 1]);
return ret;
}
int query(std::string s) {
std::vector<int> v;
std::vector<int> ptr(2);
for (char c: s) {
if (c == '0' || c == '1') {
int d = (c - '0') ^ z;
assert(ptr[d] < (int)lst[d].size());
v.push_back(lst[d][ptr[d]++]);
} else {
int l = c - 'A';
v.push_back(toQ[l]);
}
}
return use_machine(v);
}
map<vector<int>, string> prec1 = {
{{}, "A0B0C0DE"},
{{1}, "CED"},
{{2}, "DBE0A"},
{{3}, "CB0E0DA1"},
{{4}, "D0A0E0CB1"},
{{5}, "DBCE1"},
{{6}, "CED"}
};
map<vector<int>, string> prec2 = {
{{}, "ABCDE0"},
{{1}, "B0"},
{{1, 1}, "EADC"},
{{2}, "CB0D"},
{{2, 1}, "EADB"},
{{2, 2}, "DAE0CB"},
{{3}, "CB0D"},
{{3, 1}, "EDB0"},
{{3, 2}, "AED"},
{{3, 3}, "ED"},
{{4}, "B0"},
{{4, 1}, "0EACD"}
};
void magic(map<vector<int>, string> &m) {
toQ.clear();
for (int i = 0; i < 5; ++i) toQ.push_back(p + i);
std::vector<int> seq;
std::map<std::string, int> res;
while (m.count(seq)) {
std::string s = m[seq];
int x = query(s);
res[s] = x;
seq.push_back(x);
}
std::vector<int> goodM;
for (int mask = 0; mask < 32; ++mask) {
bool ok = true;
for (auto w: res) ok &= eval(subs(w.first, mask)) == w.second;
if (ok) goodM.push_back(mask);
}
assert(goodM.size() == 1);
int mask = goodM[0];
for (int i = 0; i < 5; ++i) label(p++, ((mask >> i) & 1) ^ z);
}
int count_mushrooms(int n) {
labels = std::vector<int>(n, -1);
lst = std::vector<std::vector<int>>(2);
p = 1;
ans = 0;
label(0, 0);
while (p < n) {
z = lst[0].size() > lst[1].size() ? 0 : 1;
if (n - p < 5 || (int)lst[z].size() >= K) {
std::vector<int> m;
int i = 0;
while (p < n && i < (int)lst[z].size()) {
m.push_back(p++);
m.push_back(lst[z][i++]);
}
int x = use_machine(m);
lst[z ^ (x & 1)].push_back(m[0]);
x = (x + 1) / 2;
ans += (z ? x : i - x);
} else magic(!lst[z ^ 1].empty() && lst[z].size() >= 3 ? prec1 : prec2);
}
return ans;
}
