#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
vector<int> Merge(vector<int> base, vector<int> Eval) {
assert(Eval.size() <= base.size());
vector<int> ret(Eval.size() + base.size());
int id = ret.size() - 1;
while (id >= 0) {
if (Eval.size()) {
ret[id--] = Eval.back();
Eval.pop_back();
}
ret[id--] = base.back();
base.pop_back();
}
return ret;
};
tuple<int, int, int, int> calc(vector<int> A_know, vector<int> B_know, vector<int> evaluating_tokens) {
assert(evaluating_tokens.size());
assert(evaluating_tokens.size() <= max(A_know.size(), B_know.size()));
int last_token = evaluating_tokens.back();
int last_token_value = -1;
int total_A_zero = 0;
int total_B_one = 0;
if (A_know.size() >= B_know.size()) {
int val = use_machine(Merge(A_know, evaluating_tokens));
last_token_value = val & 1;
total_B_one = val - (val & 1) >> 1;
total_A_zero = evaluating_tokens.size() - 1 - total_B_one;
} else {
int val = use_machine(Merge(B_know, evaluating_tokens));
last_token_value = val & 1 ^ 1;
total_A_zero = val - (val & 1) >> 1;
total_B_one = evaluating_tokens.size() - 1 - total_A_zero;
}
return make_tuple(total_A_zero, total_B_one, last_token, last_token_value);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int total_A = 1;
pair<vector<int>, vector<int>> Exploring(vector<int> A_know, vector<int> B_know, vector<int> evaluating_tokens, int total_A_zero) {
vector<int> A_ret;
vector<int> B_ret;
shuffle(evaluating_tokens.begin(), evaluating_tokens.end(), rng);
if (total_A_zero == int(evaluating_tokens.size())) {
A_ret = evaluating_tokens;
return make_pair(A_ret, B_ret);
} else if (total_A_zero == 0) {
B_ret = evaluating_tokens;
return make_pair(A_ret, B_ret);
}
int tokens = evaluating_tokens.size();
int A_sum = total_A_zero;
int try_tokens = tokens / 2;
if (try_tokens & 1 && tokens & 1) try_tokens++;
vector<int> Trying_tokens = vector<int>(evaluating_tokens.begin(), evaluating_tokens.begin() + try_tokens);
vector<int> Left_tokens = vector<int>(evaluating_tokens.begin() + try_tokens, evaluating_tokens.end());
auto [Trying_A_zeros, Trying_B_ones, last_token, last_token_value] = calc(A_know, B_know, Trying_tokens);
if (last_token_value == 0) A_ret.push_back(last_token);
else B_ret.push_back(last_token);
Trying_tokens.pop_back();
auto [AA, BB] = Exploring(A_know, B_know, Trying_tokens, Trying_A_zeros);
auto [AAA, BBB] = Exploring(A_know, B_know, Left_tokens, total_A_zero - (last_token_value == 0) - Trying_A_zeros);
for (int i : AA) A_ret.push_back(i);
for (int i : AAA) A_ret.push_back(i);
for (int i : BB) B_ret.push_back(i);
for (int i : BBB) B_ret.push_back(i);
return make_pair(A_ret, B_ret);
}
void Absorb(vector<int> &A_know, vector<int> &B_know, vector<int> evaluating_tokens) {
assert(evaluating_tokens.size());
auto [total_A_zero, total_B_one, last_token, last_token_value] = calc(A_know, B_know, evaluating_tokens);
evaluating_tokens.pop_back();
if (last_token_value == 0) A_know.push_back(last_token);
else B_know.push_back(last_token);
auto [A, B] = Exploring(A_know, B_know, evaluating_tokens, total_A_zero);
for (int i : A) A_know.push_back(i);
for (int i : B) B_know.push_back(i);
total_A += A.size() + (last_token_value == 0);
}
vector<int> Hidden(vector<int> r, vector<int> Move) {
for (int &i : Move) {
if (i < 2) continue;
i = r[i - 2];
}
return Move;
}
int machine(vector<int> hidden) {
int cur = 0;
for (int i = 0; i < hidden.size() - 1; i++) cur += hidden[i] != hidden[i + 1];
return cur;
}
vector<int> first_move = {2, 3, 4, 0, 1, 5, 1, 1, 6};
vector<vector<int>> result_to_next_move = {
{0, 1, 1, 1, 2, 3, 4, 5, 6},
{0, 1, 1, 1, 2, 3, 5, 4, 6},
{1, 2, 1, 3, 1, 5, 0, 6, 4},
{1, 2, 1, 6, 1, 0, 5, 3, 4},
{0, 2, 5, 1, 1, 6, 1, 4, 3},
{0, 1, 1, 1, 2, 4, 6, 5, 3},
{0, 1, 1, 1, 2, 3, 4, 5, 6}
};
vector<int> Converse(vector<int> A_know, vector<int> B_know, vector<int> ids, int A_val, int B_val, vector<int> Move) {
assert(count(Move.begin(), Move.end(), A_val) <= A_know.size() && count(Move.begin(), Move.end(), B_val) <= B_know.size());
for (int &i : Move) {
if (i >= 2) i = ids[i - 2];
else if (i == A_val) {
i = A_know.back();
A_know.pop_back();
} else {
i = B_know.back();
B_know.pop_back();
}
}
return Move;
}
vector<int> mask_to_vec(int msk, int sz) {
vector<int> r;
for (int i = 0; i < sz; i++) {
r.push_back(msk >> i & 1);
}
return r;
}
pair<int, int> unique_value(vector<int> r) {
assert(r.size() == 5);
int first = machine(Hidden(r, first_move));
vector<int> second_move = result_to_next_move[first - 1];
int second = machine(Hidden(r, second_move));
return make_pair(first, second);
}
vector<int> Short_explore(vector<int> A_know, vector<int> B_know, vector<int> ids) {
int A_val, B_val;
assert(ids.size() == 5);
assert(max(A_know.size(), B_know.size()) >= 3 && min(A_know.size(), B_know.size()) >= 1);
if (A_know.size() >= 3) {
A_val = 1;
B_val = 0;
} else {
B_val = 1;
A_val = 0;
}
vector<int> F = Converse(A_know, B_know, ids, A_val, B_val, first_move);
int result = use_machine(F);
vector<int> S = result_to_next_move[result - 1];
S = Converse(A_know, B_know, ids, A_val, B_val, S);
int result2 = use_machine(S);
for (int msk = 0; msk < (1 << 5); msk++) {
vector<int> r = mask_to_vec(msk, 5);
auto [f, s] = unique_value(r);
if (f == result && s == result2) {
for (int &i : r) i ^= A_val;
return r;
}
}
assert(false);
}
int skip_to_max = 90;
int count_mushrooms(int n) {
vector<int> A_know = {0};
vector<int> B_know;
vector<int> untouched(n - 1);
iota(untouched.begin(), untouched.end(), 1);
shuffle(untouched.begin(), untouched.end(), rng);
int ptr = 0;
if (n <= 220) {
while (ptr < n - 1) {
vector<int> foo = {untouched[ptr]};
Absorb(A_know, B_know, foo);
ptr++;
}
return total_A;
}
while (max(A_know.size(), B_know.size()) < 3 || min(A_know.size(), B_know.size()) < 1) {
int try_tokens = min(2, int(max(A_know.size(), B_know.size())));
vector<int> foo = vector<int>(untouched.begin() + ptr, untouched.begin() + ptr + try_tokens);
ptr += try_tokens;
Absorb(A_know, B_know, foo);
if (max(A_know.size(), B_know.size()) >= skip_to_max) break;
}
while (A_know.size() + B_know.size() < 2 * skip_to_max) {
int try_tokens = 5;
vector<int> foo = vector<int>(untouched.begin() + ptr, untouched.begin() + ptr + try_tokens);
vector<int> unveil = Short_explore(A_know, B_know, foo);
for (int i = 0; i < try_tokens; i++) {
total_A += unveil[i] == 0;
if (unveil[i] == 0) A_know.push_back(foo[i]);
else B_know.push_back(foo[i]);
}
ptr += try_tokens;
}
while (ptr < n - 1) {
int try_tokens = max(A_know.size(), B_know.size());
try_tokens = min(try_tokens, n - 1 - ptr);
vector<int> foo = vector<int>(untouched.begin() + ptr, untouched.begin() + ptr + try_tokens);
ptr += try_tokens;
auto [total_A_zero, total_B_one, last_token, last_token_value] = calc(A_know, B_know, foo);
total_A += total_A_zero + (last_token_value == 0);
if (last_token_value == 0) A_know.push_back(last_token);
else B_know.push_back(last_token);
}
return total_A;
}
