#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
const int N = 100;
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;
}
}
}
}
}
}
const int num = 2e6;
vector<int> Round_up_sqrt(num);
void prep_sqrt() {
int cur = 0;
for (int i = 0; i < int(Round_up_sqrt.size()); i++) {
if (cur * cur <= i) cur++;
Round_up_sqrt[i] = cur;
}
}
int Calc_min_move(int mx, int token_left) {
int x = Round_up_sqrt[token_left + mx * mx] - mx - 1;
int len = 2 * x + 1;
int cur_sum = mx * len + x * (x + 1);
while (cur_sum < token_left) {
len++;
cur_sum += mx + len / 2;
}
return len;
}
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 = Try_to_explore_tokens[tokens][A_sum];
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 skip_to_max = 90;
int count_mushrooms(int n) {
prepare_explore();
prep_sqrt();
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;
int total_A = 1;
while (ptr < n - 1) {
int try_token = min(max(A_know.size(), B_know.size()), untouched.size() - ptr);
if (int(max(A_know.size(), B_know.size())) < skip_to_max) try_token = min(try_token, 7);
vector<int> evaluating_tokens = vector<int>(untouched.begin() + ptr, untouched.begin() + ptr + try_token);
ptr += try_token;
auto [total_A_zero, total_B_one, last_token, last_token_value] = calc(A_know, B_know, evaluating_tokens);
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);
evaluating_tokens.pop_back();
if (int(max(A_know.size(), B_know.size())) < skip_to_max) {
auto [As, Bs] = Exploring(A_know, B_know, evaluating_tokens, total_A_zero);
for (int i : As) A_know.push_back(i);
for (int i : Bs) B_know.push_back(i);
} else {
if (last_token_value == 0) A_know.push_back(last_token);
else B_know.push_back(last_token);
}
}
return total_A;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
