#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e4 + 20;
const int lim = 100;
vector<int> type[maxn];
int n, res, pt;
void alternate(int k) {
k = min(min(k, n - pt), max((int)type[0].size(), (int)type[1].size()));
if (k == 0) {
return;
}
int t = (int)type[0].size() >= k ? 0 : 1;
vector<int> q;
for (int i = 0; i < k; i++) {
q.push_back(type[t][i]);
q.push_back(pt + i);
}
int cnt = use_machine(q);
if (t == 0) {
res += k - (cnt + 1) / 2;
}
else {
res += (cnt + 1) / 2;
}
type[t ^ (cnt & 1)].push_back(pt + k - 1);
if ((cnt >> 1) == (k - 1)) {
for (int i = 0; i < k - 1; i++) {
type[t ^ 1].push_back(pt + i);
}
}
else if ((cnt >> 1) == 0) {
for (int i = 0; i < k - 1; i++) {
type[t].push_back(pt + i);
}
}
else if (k == 3 && pt + 5 <= n) {
if ((int)type[t ^ 1].size() < 2) {
alternate(2);
res -= 1;
pt -= 2;
}
else {
cnt = use_machine({type[t ^ 1][0], pt, type[t ^ 1][1], type[t][0], pt + 1, type[t][1], pt + 3, type[t][2], pt + 4}) - 1;
res += (t ^ (cnt & 1) ^ 1);
res += (t ^ ((cnt >> 1) & 1) ^ 1);
type[t ^ (cnt & 1)].push_back(pt + 4);
type[t ^ ((cnt >> 1) & 1)].push_back(pt + 3);
type[t ^ 1 ^ ((cnt >> 2) & 1)].push_back(pt);
type[t ^ ((cnt >> 2) & 1)].push_back(pt + 1);
pt += 2;
}
}
pt += k;
}
int count_mushrooms(int _n) {
n = _n;
type[0].push_back(0);
res = 1;
pt = 1;
alternate(1);
alternate(1);
alternate(2);
while (pt < n && (int)type[0].size() < lim && (int)type[1].size() < lim) {
alternate(3);
}
while (pt < n) {
alternate(n);
}
return res;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
720 KB |
Output is correct |
| 2 |
Correct |
1 ms |
720 KB |
Output is correct |
| 3 |
Correct |
1 ms |
720 KB |
Output is correct |
| 4 |
Correct |
1 ms |
720 KB |
Output is correct |
| 5 |
Correct |
1 ms |
720 KB |
Output is correct |
| 6 |
Correct |
2 ms |
720 KB |
Output is correct |
| 7 |
Correct |
4 ms |
916 KB |
Output is correct |
| 8 |
Correct |
4 ms |
848 KB |
Output is correct |
| 9 |
Correct |
5 ms |
720 KB |
Output is correct |
| 10 |
Correct |
6 ms |
720 KB |
Output is correct |
| 11 |
Correct |
5 ms |
776 KB |
Output is correct |
| 12 |
Correct |
5 ms |
720 KB |
Output is correct |
| 13 |
Correct |
5 ms |
720 KB |
Output is correct |
| 14 |
Correct |
4 ms |
720 KB |
Output is correct |
| 15 |
Correct |
5 ms |
772 KB |
Output is correct |
| 16 |
Correct |
5 ms |
792 KB |
Output is correct |
| 17 |
Correct |
3 ms |
720 KB |
Output is correct |
| 18 |
Correct |
5 ms |
772 KB |
Output is correct |
| 19 |
Correct |
5 ms |
720 KB |
Output is correct |
| 20 |
Correct |
5 ms |
720 KB |
Output is correct |
| 21 |
Correct |
5 ms |
788 KB |
Output is correct |
| 22 |
Correct |
5 ms |
792 KB |
Output is correct |
| 23 |
Correct |
4 ms |
720 KB |
Output is correct |
| 24 |
Correct |
4 ms |
780 KB |
Output is correct |
| 25 |
Correct |
6 ms |
720 KB |
Output is correct |
| 26 |
Correct |
5 ms |
720 KB |
Output is correct |
| 27 |
Correct |
5 ms |
720 KB |
Output is correct |
| 28 |
Correct |
6 ms |
720 KB |
Output is correct |
| 29 |
Correct |
5 ms |
720 KB |
Output is correct |
| 30 |
Correct |
7 ms |
776 KB |
Output is correct |
| 31 |
Correct |
5 ms |
788 KB |
Output is correct |
| 32 |
Correct |
5 ms |
720 KB |
Output is correct |
| 33 |
Correct |
7 ms |
788 KB |
Output is correct |
| 34 |
Correct |
5 ms |
780 KB |
Output is correct |
| 35 |
Correct |
5 ms |
720 KB |
Output is correct |
| 36 |
Correct |
6 ms |
720 KB |
Output is correct |
| 37 |
Correct |
5 ms |
720 KB |
Output is correct |
| 38 |
Correct |
5 ms |
792 KB |
Output is correct |
| 39 |
Correct |
7 ms |
720 KB |
Output is correct |
| 40 |
Correct |
7 ms |
784 KB |
Output is correct |
| 41 |
Correct |
5 ms |
720 KB |
Output is correct |
| 42 |
Correct |
6 ms |
784 KB |
Output is correct |
| 43 |
Correct |
5 ms |
788 KB |
Output is correct |
| 44 |
Correct |
5 ms |
784 KB |
Output is correct |
| 45 |
Correct |
10 ms |
784 KB |
Output is correct |
| 46 |
Correct |
7 ms |
776 KB |
Output is correct |
| 47 |
Correct |
6 ms |
788 KB |
Output is correct |
| 48 |
Correct |
5 ms |
720 KB |
Output is correct |
| 49 |
Correct |
6 ms |
780 KB |
Output is correct |
| 50 |
Correct |
7 ms |
720 KB |
Output is correct |
| 51 |
Correct |
6 ms |
720 KB |
Output is correct |
| 52 |
Correct |
5 ms |
720 KB |
Output is correct |
| 53 |
Correct |
6 ms |
720 KB |
Output is correct |
| 54 |
Correct |
5 ms |
792 KB |
Output is correct |
| 55 |
Correct |
6 ms |
776 KB |
Output is correct |
| 56 |
Correct |
7 ms |
720 KB |
Output is correct |
| 57 |
Correct |
9 ms |
792 KB |
Output is correct |
| 58 |
Correct |
5 ms |
720 KB |
Output is correct |
| 59 |
Correct |
4 ms |
772 KB |
Output is correct |
| 60 |
Correct |
5 ms |
720 KB |
Output is correct |
| 61 |
Correct |
6 ms |
720 KB |
Output is correct |
| 62 |
Correct |
1 ms |
720 KB |
Output is correct |
| 63 |
Correct |
0 ms |
720 KB |
Output is correct |
| 64 |
Correct |
1 ms |
720 KB |
Output is correct |
| 65 |
Correct |
1 ms |
772 KB |
Output is correct |
| 66 |
Correct |
1 ms |
720 KB |
Output is correct |
| 67 |
Correct |
1 ms |
720 KB |
Output is correct |
| 68 |
Correct |
1 ms |
720 KB |
Output is correct |
| 69 |
Correct |
1 ms |
720 KB |
Output is correct |
| 70 |
Correct |
0 ms |
720 KB |
Output is correct |
| 71 |
Correct |
1 ms |
720 KB |
Output is correct |
| 72 |
Correct |
1 ms |
720 KB |
Output is correct |
| 73 |
Correct |
1 ms |
720 KB |
Output is correct |
| 74 |
Correct |
1 ms |
720 KB |
Output is correct |
| 75 |
Correct |
1 ms |
720 KB |
Output is correct |
| 76 |
Correct |
1 ms |
720 KB |
Output is correct |
| 77 |
Correct |
1 ms |
720 KB |
Output is correct |
| 78 |
Correct |
1 ms |
720 KB |
Output is correct |
| 79 |
Correct |
1 ms |
720 KB |
Output is correct |
| 80 |
Correct |
1 ms |
720 KB |
Output is correct |
| 81 |
Correct |
1 ms |
720 KB |
Output is correct |
| 82 |
Correct |
1 ms |
720 KB |
Output is correct |
| 83 |
Correct |
1 ms |
720 KB |
Output is correct |
| 84 |
Correct |
1 ms |
720 KB |
Output is correct |
| 85 |
Correct |
0 ms |
720 KB |
Output is correct |
| 86 |
Correct |
1 ms |
720 KB |
Output is correct |
| 87 |
Correct |
1 ms |
720 KB |
Output is correct |
| 88 |
Correct |
1 ms |
720 KB |
Output is correct |
| 89 |
Correct |
1 ms |
720 KB |
Output is correct |
| 90 |
Correct |
1 ms |
720 KB |
Output is correct |
| 91 |
Correct |
1 ms |
720 KB |
Output is correct |
