#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
int count_mushrooms(int N) {
if (N <= 5) {
int ans = N;
for (int i = 1; i < N; i++) {
ans -= use_machine({0, i});
}
return ans;
}
vector<int> T[] = {{0}, {}};
T[use_machine({0, 1})].push_back(1);
T[use_machine({0, 2})].push_back(2);
int z = T[1].size() >= 2, i = 3, x;
x = use_machine({T[z][0], i, T[z][1], i + 1});
T[x >> 1 & 1 ^ z].push_back(i++);
T[x >> 0 & 1 ^ z].push_back(i++);
while (i + 2 < N && i <= 200 && (T[0].size() < 2 || T[1].size() < 2)) {
z = T[1].size() >= 3;
x = use_machine({T[z][0], i + 1, T[z][1], i + 2, T[z][2], i});
T[x & 1 ^ z].push_back(i++);
if (~x & 2) {
T[x >> 2 & 1 ^ z].push_back(i++);
T[x >> 2 & 1 ^ z].push_back(i++);
} else {
x = use_machine({0, i});
T[x ^ 0].push_back(i++);
T[x ^ 1].push_back(i++);
}
}
for (z = T[1].size() >= 3; i + 4 < N && i <= 200;) {
x = use_machine({T[z][0], i + 1, T[z][1], i + 2, T[z][2], i});
T[x & 1 ^ z].push_back(i++);
if (~x & 2) {
T[x >> 2 & 1 ^ z].push_back(i++);
T[x >> 2 & 1 ^ z].push_back(i++);
} else {
x = use_machine({T[z ^ 1][0], i, T[z ^ 1][1], T[z][0], i + 1, T[z][1], i + 2, T[z][2], i + 3}) - 1;
T[x >> 2 & 1 ^ z ^ 1].push_back(i++);
T[x >> 2 & 1 ^ z].push_back(i++);
T[x >> 1 & 1 ^ z].push_back(i++);
T[x >> 0 & 1 ^ z].push_back(i++);
}
}
int ans = T[0].size();
while (i < N) {
z = T[1].size() > T[0].size();
int K = min(N - i, (int)T[z].size());
vector<int> v;
for (int j = 0; j < K; j++) {
v.push_back(T[z][j]);
v.push_back(i++);
}
x = use_machine(v);
if (z) {
ans += x / 2 + x % 2;
} else {
ans += K - x / 2 - x % 2;
}
T[x & 1 ^ z].push_back(i - 1);
}
return ans;
}
Compilation message
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:17:14: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
17 | T[x >> 1 & 1 ^ z].push_back(i++);
| ~~~~~~~^~~
mushrooms.cpp:18:14: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
18 | T[x >> 0 & 1 ^ z].push_back(i++);
| ~~~~~~~^~~
mushrooms.cpp:22:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
22 | T[x & 1 ^ z].push_back(i++);
| ~~^~~
mushrooms.cpp:24:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
24 | T[x >> 2 & 1 ^ z].push_back(i++);
| ~~~~~~~^~~
mushrooms.cpp:25:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
25 | T[x >> 2 & 1 ^ z].push_back(i++);
| ~~~~~~~^~~
mushrooms.cpp:34:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
34 | T[x & 1 ^ z].push_back(i++);
| ~~^~~
mushrooms.cpp:36:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
36 | T[x >> 2 & 1 ^ z].push_back(i++);
| ~~~~~~~^~~
mushrooms.cpp:37:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
37 | T[x >> 2 & 1 ^ z].push_back(i++);
| ~~~~~~~^~~
mushrooms.cpp:40:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
40 | T[x >> 2 & 1 ^ z ^ 1].push_back(i++);
| ~~~~~~~^~~
mushrooms.cpp:41:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
41 | T[x >> 2 & 1 ^ z].push_back(i++);
| ~~~~~~~^~~
mushrooms.cpp:42:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
42 | T[x >> 1 & 1 ^ z].push_back(i++);
| ~~~~~~~^~~
mushrooms.cpp:43:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
43 | T[x >> 0 & 1 ^ z].push_back(i++);
| ~~~~~~~^~~
mushrooms.cpp:61:13: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
61 | T[x & 1 ^ z].push_back(i - 1);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
1 ms |
208 KB |
Output is correct |
| 4 |
Correct |
0 ms |
208 KB |
Output is correct |
| 5 |
Correct |
1 ms |
308 KB |
Output is correct |
| 6 |
Correct |
2 ms |
312 KB |
Output is correct |
| 7 |
Correct |
6 ms |
208 KB |
Output is correct |
| 8 |
Correct |
7 ms |
208 KB |
Output is correct |
| 9 |
Correct |
6 ms |
208 KB |
Output is correct |
| 10 |
Correct |
5 ms |
208 KB |
Output is correct |
| 11 |
Correct |
6 ms |
248 KB |
Output is correct |
| 12 |
Correct |
7 ms |
308 KB |
Output is correct |
| 13 |
Correct |
7 ms |
208 KB |
Output is correct |
| 14 |
Correct |
4 ms |
316 KB |
Output is correct |
| 15 |
Correct |
5 ms |
324 KB |
Output is correct |
| 16 |
Correct |
5 ms |
312 KB |
Output is correct |
| 17 |
Correct |
3 ms |
304 KB |
Output is correct |
| 18 |
Correct |
6 ms |
316 KB |
Output is correct |
| 19 |
Correct |
5 ms |
208 KB |
Output is correct |
| 20 |
Correct |
5 ms |
208 KB |
Output is correct |
| 21 |
Correct |
5 ms |
208 KB |
Output is correct |
| 22 |
Correct |
5 ms |
324 KB |
Output is correct |
| 23 |
Correct |
5 ms |
208 KB |
Output is correct |
| 24 |
Correct |
5 ms |
320 KB |
Output is correct |
| 25 |
Correct |
7 ms |
208 KB |
Output is correct |
| 26 |
Correct |
6 ms |
320 KB |
Output is correct |
| 27 |
Correct |
4 ms |
316 KB |
Output is correct |
| 28 |
Correct |
6 ms |
320 KB |
Output is correct |
| 29 |
Correct |
6 ms |
320 KB |
Output is correct |
| 30 |
Correct |
6 ms |
324 KB |
Output is correct |
| 31 |
Correct |
5 ms |
320 KB |
Output is correct |
| 32 |
Correct |
6 ms |
316 KB |
Output is correct |
| 33 |
Correct |
4 ms |
208 KB |
Output is correct |
| 34 |
Correct |
7 ms |
308 KB |
Output is correct |
| 35 |
Correct |
7 ms |
312 KB |
Output is correct |
| 36 |
Correct |
6 ms |
308 KB |
Output is correct |
| 37 |
Correct |
5 ms |
208 KB |
Output is correct |
| 38 |
Correct |
6 ms |
332 KB |
Output is correct |
| 39 |
Correct |
5 ms |
208 KB |
Output is correct |
| 40 |
Correct |
5 ms |
312 KB |
Output is correct |
| 41 |
Correct |
6 ms |
308 KB |
Output is correct |
| 42 |
Correct |
6 ms |
208 KB |
Output is correct |
| 43 |
Correct |
6 ms |
328 KB |
Output is correct |
| 44 |
Correct |
5 ms |
208 KB |
Output is correct |
| 45 |
Correct |
5 ms |
208 KB |
Output is correct |
| 46 |
Correct |
7 ms |
208 KB |
Output is correct |
| 47 |
Correct |
7 ms |
324 KB |
Output is correct |
| 48 |
Correct |
4 ms |
320 KB |
Output is correct |
| 49 |
Correct |
4 ms |
324 KB |
Output is correct |
| 50 |
Correct |
6 ms |
208 KB |
Output is correct |
| 51 |
Correct |
5 ms |
328 KB |
Output is correct |
| 52 |
Correct |
6 ms |
208 KB |
Output is correct |
| 53 |
Correct |
7 ms |
208 KB |
Output is correct |
| 54 |
Correct |
5 ms |
304 KB |
Output is correct |
| 55 |
Correct |
6 ms |
324 KB |
Output is correct |
| 56 |
Correct |
5 ms |
312 KB |
Output is correct |
| 57 |
Correct |
6 ms |
208 KB |
Output is correct |
| 58 |
Correct |
5 ms |
320 KB |
Output is correct |
| 59 |
Correct |
4 ms |
208 KB |
Output is correct |
| 60 |
Correct |
7 ms |
320 KB |
Output is correct |
| 61 |
Correct |
7 ms |
308 KB |
Output is correct |
| 62 |
Correct |
0 ms |
208 KB |
Output is correct |
| 63 |
Correct |
1 ms |
208 KB |
Output is correct |
| 64 |
Correct |
1 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 |
256 KB |
Output is correct |
| 68 |
Correct |
0 ms |
208 KB |
Output is correct |
| 69 |
Correct |
0 ms |
208 KB |
Output is correct |
| 70 |
Correct |
0 ms |
208 KB |
Output is correct |
| 71 |
Correct |
1 ms |
208 KB |
Output is correct |
| 72 |
Correct |
0 ms |
208 KB |
Output is correct |
| 73 |
Correct |
0 ms |
208 KB |
Output is correct |
| 74 |
Correct |
0 ms |
208 KB |
Output is correct |
| 75 |
Correct |
0 ms |
208 KB |
Output is correct |
| 76 |
Correct |
0 ms |
208 KB |
Output is correct |
| 77 |
Correct |
1 ms |
208 KB |
Output is correct |
| 78 |
Correct |
0 ms |
208 KB |
Output is correct |
| 79 |
Correct |
1 ms |
208 KB |
Output is correct |
| 80 |
Correct |
1 ms |
208 KB |
Output is correct |
| 81 |
Correct |
0 ms |
208 KB |
Output is correct |
| 82 |
Correct |
1 ms |
208 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 |
0 ms |
208 KB |
Output is correct |
| 87 |
Correct |
0 ms |
208 KB |
Output is correct |
| 88 |
Correct |
0 ms |
208 KB |
Output is correct |
| 89 |
Correct |
0 ms |
208 KB |
Output is correct |
| 90 |
Correct |
1 ms |
208 KB |
Output is correct |
| 91 |
Correct |
0 ms |
208 KB |
Output is correct |
