#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}
template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
res += static_cast<char>('0' + v[i]);
}
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);
const int N = 150;
vector<vector<int>> explore_cost_of_tokens_with_A_sum(N + 1, vector<int>(N + 1, INT_MAX));
vector<vector<int>> Try_to_explore_tokens(N + 1, vector<int>(N + 1, -1));
void prepare_explore() {
explore_cost_of_tokens_with_A_sum[0][0] = 0;
for (int tokens = 1; tokens <= N; tokens++) {
for (int A_sum = 0; A_sum <= tokens; A_sum++) {
if (A_sum == 0 || A_sum == tokens) explore_cost_of_tokens_with_A_sum[tokens][A_sum] = 0;
else {
for (int try_tokens = 1; try_tokens < tokens; try_tokens++) {
int worst_cost = 0;
for (int what_A = 0; what_A <= min(A_sum, try_tokens); what_A++) {
if (what_A > 0) {
worst_cost = max(worst_cost, explore_cost_of_tokens_with_A_sum[try_tokens - 1][what_A - 1] + 1 + explore_cost_of_tokens_with_A_sum[tokens - try_tokens][A_sum - what_A]);
}
if (what_A < try_tokens) {
worst_cost = max(worst_cost, explore_cost_of_tokens_with_A_sum[try_tokens - 1][what_A] + 1 + explore_cost_of_tokens_with_A_sum[tokens - try_tokens][A_sum - what_A]);
}
}
if (explore_cost_of_tokens_with_A_sum[tokens][A_sum] > worst_cost) {
Try_to_explore_tokens[tokens][A_sum] = try_tokens;
explore_cost_of_tokens_with_A_sum[tokens][A_sum] = worst_cost;
}
}
}
}
}
}
vector<int> mushrooms;
int used = 0;
int pre = 0;
int use_machine(vector<int> x) {
used++;
int ret = 0;
for (int i : x) if (mushrooms[i] == -1) {
mushrooms[i] = pre ^ 1;
pre ^= 1;
}
for (int i = 0; i < int(x.size()) - 1; i++) {
ret += (mushrooms[x[i]] != mushrooms[x[i + 1]]);
}
return ret;
}
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());
// generate random number between l, r : uniform_int_distribution<long long>(l, r)(rng)
// random shuffle : shuffle(.begin(), .end(), rng)
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;
assert(tokens <= N);
int try_tokens = tokens / 2;
if (try_tokens & 1 && tokens & 1) try_tokens++;
assert(try_tokens > 0 && try_tokens < 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);
}
int total_A = 1;
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);
}
int skip_to_max = 60;
int count_mushrooms(int n) {
prepare_explore();
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()) < skip_to_max) {
int try_tokens = max(A_know.size(), B_know.size());
try_tokens = min(try_tokens, 2 * skip_to_max - int(A_know.size() + B_know.size()));
if (try_tokens & 1 && try_tokens > 1) try_tokens--;
vector<int> foo = vector<int>(untouched.begin() + ptr, untouched.begin() + ptr + try_tokens);
int pre_used = used;
ptr += try_tokens;
Absorb(A_know, B_know, foo);
}
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;
}
