#include "mushrooms.h"
#include <bits/stdc++.h>
struct Grid {
int size;
int index;
std::vector <std::bitset <512>> arr;
};
std::vector <Grid> grids(8);
std::vector <int> dac(std::vector <int> input, int depth) {
if (!depth) {
return input;
}
std::vector <int> interm[2], output[3];
int acc[2] = { input[(int) input.size() - 2], 0 };
for (int i = 0; i < (int) input.size() - 2; i += 2) {
interm[0].push_back((input[i] + input[i + 1] - acc[0]) >> 1);
interm[1].push_back((input[i + 1] - (input[i] - acc[0])) >> 1);
output[1].push_back((input[i] + input[i + 1] - acc[0]) & 1);
acc[1] += output[1].back();
}
interm[0].push_back(input[(int) input.size() - 1] - input[(int) input.size() - 2] - acc[1]);
interm[1].push_back(input[(int) input.size() - 2]);
output[0] = dac(interm[0], depth - 1);
output[2] = dac(interm[1], depth - 1);
output[0].insert(output[0].end(), output[2].begin(), output[2].end());
output[0].insert(output[0].end(), output[1].begin(), output[1].end());
return output[0];
}
std::vector <int> dp(210), start(210);
void prep() {
grids[0].size = 1;
grids[0].index = 3;
grids[0].arr.push_back(1);
for (int i = 1; i <= 7; i++) {
int shift = grids[i - 1].size;
grids[i].size = (shift << 1) + (1 << (i - 1)) - 1;
for (int j = 0; j < (int) grids[i - 1].arr.size() - 1; j++) {
grids[i].arr.push_back(grids[i - 1].arr[j] | ((grids[i - 1].arr.back() ^ grids[i - 1].arr[j]) << shift));
grids[i].arr.push_back(grids[i - 1].arr[j] | (grids[i - 1].arr[j] << shift) | (std::bitset <512> (1) << ((shift << 1) + j)));
}
grids[i].arr.emplace_back(grids[i - 1].arr.back() << shift);
grids[i].arr.emplace_back(std::string(grids[i].size, '1'));
std::vector <int> order;
for (int j = 0; j < (int) grids[i].arr.size(); j++) {
order.push_back(grids[i].arr[j].count());
}
order[(1 << i) - 1] -= order[(1 << i) - 2];
std::sort(order.begin(), order.end());
int count = 0;
for (int j = 0; j < (int) order.size(); j++) {
count = std::max(count, ((order[j] << 1) | 1) - j);
}
grids[i].index = count;
}
std::iota(dp.begin(), dp.begin() + 3, 1);
for (int i = 2; i < 203; i++) {
for (int j = 0; j <= 7; j++) {
if (dp[i] >= grids[j].index && (1 << j) + i <= 203 && dp[i] + grids[j].size > dp[(1 << j) + i]) {
dp[(1 << j) + i] = dp[i] + grids[j].size + (1 << j);
start[(1 << j) + i] = j;
}
}
}
}
int count_mushrooms(int n) {
if (n == 2) {
return 2 - use_machine({ 0, 1 });
}
prep();
int ans = 1, index = 0;
for (int i = 2, now = dp[2]; i <= 203 && dp[i] <= n; now = dp[++i]) {
for (int j = 0; j < 203 - i; j++) {
now += ((dp[i] + j - 1) >> 1) + 1;
}
if (now > ans) {
ans = now;
index = i;
}
}
std::vector <int> order;
for (int i = index; i != 2; i -= 1 << start[i]) {
order.push_back(start[i]);
}
std::reverse(order.begin(), order.end());
std::vector <int> eo[2];
int l = 1;
eo[0].push_back(0);
for (int i = 0; i < 2; i++) {
eo[use_machine({ 0, l })].push_back(l++);
}
for (int i : order) {
std::vector <int> idx(1 << i);
std::iota(idx.begin(), idx.end(), 0);
std::sort(idx.begin(), idx.end(), [&] (int u, int v) -> bool { return grids[i].arr[u].count() < grids[i].arr[v].count(); });
std::vector <int> result(1 << i);
for (int k = 0, cn = 0; k < (1 << i); k++, cn = 0) {
auto bs = grids[i].arr[idx[k]];
if (i && idx[k] + 1 == (1 << i)) {
bs ^= grids[i].arr[idx[k] - 1];
}
std::vector <int> q = { l + grids[i].size + k, eo[eo[1].size() > eo[0].size()][cn++] };
for (int j = 0; j < grids[i].size; j++) {
if (bs[j]) {
q.push_back(j + l);
q.push_back(eo[eo[1].size() > eo[0].size()][cn++]);
}
}
int qr = use_machine(q);
result[idx[k]] = eo[0].size() >= eo[1].size() ? (qr >> 1) : (cn - 1 - (qr >> 1));
eo[(eo[0].size() >= eo[1].size()) ^ (~qr & 1)].push_back(l + grids[i].size + k);
}
if (i) {
result[(1 << i) - 1] += result[(1 << i) - 2];
}
auto value = dac(result, i);
for (int j = 0; j < grids[i].size; j++) {
eo[value[j]].push_back(l + j);
}
l += grids[i].size + (1 << i);
}
ans = eo[0].size();
for (int r; l < n; l = r) {
auto& good = eo[eo[1].size() > eo[0].size()];
r = std::min(l + (int) good.size(), n);
std::vector <int> q;
for (int i = l; i < r; i++) {
q.push_back(i);
q.push_back(good[i - l]);
}
int qr = use_machine(q);
if (eo[1].size() > eo[0].size()) {
qr = ((r - l) << 1) - qr - 1;
}
ans += (r - l) - ((qr + 1) >> 1);
eo[qr & 1].push_back(l);
l = r;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
0 ms |
208 KB |
Output is correct |
| 4 |
Correct |
1 ms |
208 KB |
Output is correct |
| 5 |
Correct |
1 ms |
208 KB |
Output is correct |
| 6 |
Correct |
3 ms |
332 KB |
Output is correct |
| 7 |
Correct |
5 ms |
336 KB |
Output is correct |
| 8 |
Correct |
5 ms |
332 KB |
Output is correct |
| 9 |
Correct |
6 ms |
336 KB |
Output is correct |
| 10 |
Correct |
6 ms |
336 KB |
Output is correct |
| 11 |
Correct |
6 ms |
336 KB |
Output is correct |
| 12 |
Correct |
6 ms |
336 KB |
Output is correct |
| 13 |
Correct |
8 ms |
340 KB |
Output is correct |
| 14 |
Correct |
4 ms |
336 KB |
Output is correct |
| 15 |
Correct |
7 ms |
340 KB |
Output is correct |
| 16 |
Correct |
6 ms |
336 KB |
Output is correct |
| 17 |
Correct |
4 ms |
336 KB |
Output is correct |
| 18 |
Correct |
6 ms |
336 KB |
Output is correct |
| 19 |
Correct |
6 ms |
336 KB |
Output is correct |
| 20 |
Correct |
7 ms |
340 KB |
Output is correct |
| 21 |
Correct |
6 ms |
336 KB |
Output is correct |
| 22 |
Correct |
8 ms |
336 KB |
Output is correct |
| 23 |
Correct |
6 ms |
340 KB |
Output is correct |
| 24 |
Correct |
5 ms |
336 KB |
Output is correct |
| 25 |
Correct |
8 ms |
336 KB |
Output is correct |
| 26 |
Correct |
7 ms |
336 KB |
Output is correct |
| 27 |
Correct |
7 ms |
336 KB |
Output is correct |
| 28 |
Correct |
7 ms |
336 KB |
Output is correct |
| 29 |
Correct |
6 ms |
336 KB |
Output is correct |
| 30 |
Correct |
7 ms |
384 KB |
Output is correct |
| 31 |
Correct |
6 ms |
336 KB |
Output is correct |
| 32 |
Correct |
6 ms |
336 KB |
Output is correct |
| 33 |
Correct |
5 ms |
340 KB |
Output is correct |
| 34 |
Correct |
6 ms |
336 KB |
Output is correct |
| 35 |
Correct |
7 ms |
336 KB |
Output is correct |
| 36 |
Correct |
8 ms |
336 KB |
Output is correct |
| 37 |
Correct |
5 ms |
340 KB |
Output is correct |
| 38 |
Correct |
6 ms |
336 KB |
Output is correct |
| 39 |
Correct |
7 ms |
332 KB |
Output is correct |
| 40 |
Correct |
6 ms |
336 KB |
Output is correct |
| 41 |
Correct |
6 ms |
336 KB |
Output is correct |
| 42 |
Correct |
6 ms |
336 KB |
Output is correct |
| 43 |
Correct |
6 ms |
336 KB |
Output is correct |
| 44 |
Correct |
6 ms |
208 KB |
Output is correct |
| 45 |
Correct |
7 ms |
336 KB |
Output is correct |
| 46 |
Correct |
8 ms |
208 KB |
Output is correct |
| 47 |
Correct |
7 ms |
336 KB |
Output is correct |
| 48 |
Correct |
7 ms |
340 KB |
Output is correct |
| 49 |
Correct |
8 ms |
340 KB |
Output is correct |
| 50 |
Correct |
7 ms |
336 KB |
Output is correct |
| 51 |
Correct |
7 ms |
336 KB |
Output is correct |
| 52 |
Correct |
8 ms |
336 KB |
Output is correct |
| 53 |
Correct |
6 ms |
336 KB |
Output is correct |
| 54 |
Correct |
5 ms |
336 KB |
Output is correct |
| 55 |
Correct |
6 ms |
336 KB |
Output is correct |
| 56 |
Correct |
6 ms |
340 KB |
Output is correct |
| 57 |
Correct |
8 ms |
336 KB |
Output is correct |
| 58 |
Correct |
9 ms |
336 KB |
Output is correct |
| 59 |
Correct |
7 ms |
336 KB |
Output is correct |
| 60 |
Correct |
5 ms |
344 KB |
Output is correct |
| 61 |
Correct |
6 ms |
336 KB |
Output is correct |
| 62 |
Correct |
0 ms |
208 KB |
Output is correct |
| 63 |
Correct |
0 ms |
208 KB |
Output is correct |
| 64 |
Correct |
0 ms |
208 KB |
Output is correct |
| 65 |
Correct |
0 ms |
208 KB |
Output is correct |
| 66 |
Correct |
1 ms |
208 KB |
Output is correct |
| 67 |
Correct |
0 ms |
208 KB |
Output is correct |
| 68 |
Correct |
1 ms |
208 KB |
Output is correct |
| 69 |
Correct |
0 ms |
336 KB |
Output is correct |
| 70 |
Correct |
1 ms |
336 KB |
Output is correct |
| 71 |
Correct |
0 ms |
336 KB |
Output is correct |
| 72 |
Correct |
0 ms |
208 KB |
Output is correct |
| 73 |
Correct |
1 ms |
208 KB |
Output is correct |
| 74 |
Correct |
1 ms |
208 KB |
Output is correct |
| 75 |
Correct |
0 ms |
208 KB |
Output is correct |
| 76 |
Correct |
1 ms |
208 KB |
Output is correct |
| 77 |
Correct |
0 ms |
208 KB |
Output is correct |
| 78 |
Correct |
1 ms |
208 KB |
Output is correct |
| 79 |
Correct |
1 ms |
208 KB |
Output is correct |
| 80 |
Correct |
0 ms |
220 KB |
Output is correct |
| 81 |
Correct |
1 ms |
208 KB |
Output is correct |
| 82 |
Correct |
0 ms |
336 KB |
Output is correct |
| 83 |
Correct |
1 ms |
208 KB |
Output is correct |
| 84 |
Correct |
1 ms |
208 KB |
Output is correct |
| 85 |
Correct |
0 ms |
208 KB |
Output is correct |
| 86 |
Correct |
1 ms |
208 KB |
Output is correct |
| 87 |
Correct |
1 ms |
208 KB |
Output is correct |
| 88 |
Correct |
1 ms |
208 KB |
Output is correct |
| 89 |
Correct |
0 ms |
208 KB |
Output is correct |
| 90 |
Correct |
0 ms |
208 KB |
Output is correct |
| 91 |
Correct |
0 ms |
208 KB |
Output is correct |
