#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include "mushrooms.h"
using namespace std;
const int VAL = 95;
vector<int> a, b, missing;
map<int, vector<int>> diff, eq;
set<int> found;
void nextPos(const vector<int>& v, int& pos) {
while (pos < (int) v.size()) {
if (found.count(v[pos])) {
++pos;
} else break;
}
}
void process(int x, bool isA) {
if (found.count(x)) return;
found.insert(x);
if (isA) a.push_back(x);
else b.push_back(x);
if (diff.count(x))
for (int val : diff[x]) {
process(val, !isA);
}
if (eq.count(x))
for (int val : eq[x]) {
process(val, isA);
}
}
int count_mushrooms(int n) {
a.clear(); b.clear(); diff.clear(); found.clear(); missing.clear();
srand(time(NULL));
vector<int> v;
for (int i = 1; i < n; ++i)
v.push_back(i);
// random_shuffle(v.begin(), v.end());
int ans = 0, pos = 0;
a.push_back(0); found.insert(0);
while (a.size() < VAL && b.size() < VAL && pos + 5 <= (int) v.size()) {
if (a.size() > 2 && b.size() > 1) {
vector<int> arr;
nextPos(v, pos);
if (pos < (int) v.size()) {
arr.push_back(a[0]);
arr.push_back(v[pos]), ++pos;
}
nextPos(v, pos);
if (pos < (int) v.size()) {
arr.push_back(a[1]);
arr.push_back(v[pos]), ++pos;
}
nextPos(v, pos);
if (pos < (int) v.size()) {
arr.push_back(a[2]);
arr.push_back(v[pos]), ++pos;
}
int ret = use_machine(arr);
if (arr.size() == 2) {
if (ret == 1) {
process(arr[1], false);
} else {
process(arr[1], true);
}
exit(-1);
} else if (arr.size() == 4) {
if (ret == 3) {
process(arr[1], false);
process(arr[3], false);
} else if (ret == 2) {
process(arr[1], false);
process(arr[3], true);
} else if (ret == 1) {
process(arr[1], true);
process(arr[3], false);
} else {
process(arr[1], true);
process(arr[3], true);
}
exit(-1);
} else if (arr.size() == 6) {
if (ret == 5) {
process(arr[1], false);
process(arr[3], false);
process(arr[5], false);
} else if (ret == 4) {
process(arr[1], false);
process(arr[3], false);
process(arr[5], true);
} else if (ret == 3) {
process(arr[5], false);
vector<int> nArr = {b[1], arr[1], b[0], a[0], arr[3], a[1]};
nextPos(v, pos);
if (pos < (int) v.size()) {
nArr.push_back(v[pos]), ++pos;
nArr.push_back(a[2]);
}
nextPos(v, pos);
if (pos < (int) v.size()) {
nArr.push_back(v[pos]), ++pos;
}
int cur = use_machine(nArr) - 1;
process(arr[1], (cur & 4));
process(arr[3], !(cur & 4));
process(nArr[6], !(cur & 2));
process(nArr[8], !(cur & 1));
} else if (ret == 2) {
process(arr[5], true);
vector<int> nArr = {b[1], arr[1], b[0], a[0], arr[3], a[1]};
nextPos(v, pos);
if (pos < (int) v.size()) {
nArr.push_back(v[pos]), ++pos;
nArr.push_back(a[2]);
}
nextPos(v, pos);
if (pos < (int) v.size()) {
nArr.push_back(v[pos]), ++pos;
}
int cur = use_machine(nArr) - 1;
process(arr[1], (cur & 4));
process(arr[3], !(cur & 4));
process(nArr[6], !(cur & 2));
process(nArr[8], !(cur & 1));
} else if (ret == 1) {
process(arr[1], true);
process(arr[3], true);
process(arr[5], false);
} else {
process(arr[1], true);
process(arr[3], true);
process(arr[5], true);
}
}
} else if (b.size() > 2 && a.size() > 1) {
vector<int> arr;
nextPos(v, pos);
if (pos < (int) v.size()) {
arr.push_back(b[0]);
arr.push_back(v[pos]), ++pos;
}
nextPos(v, pos);
if (pos < (int) v.size()) {
arr.push_back(b[1]);
arr.push_back(v[pos]), ++pos;
}
nextPos(v, pos);
if (pos < (int) v.size()) {
arr.push_back(b[2]);
arr.push_back(v[pos]), ++pos;
}
int ret = use_machine(arr);
if (arr.size() == 2) {
if (ret == 1) {
process(arr[1], true);
} else {
process(arr[1], false);
}
exit(-1);
} else if (arr.size() == 4) {
if (ret == 3) {
process(arr[1], true);
process(arr[3], true);
} else if (ret == 2) {
process(arr[1], true);
process(arr[3], false);
} else if (ret == 1) {
process(arr[1], false);
process(arr[3], true);
} else {
process(arr[1], false);
process(arr[3], false);
}
exit(-1);
} else if (arr.size() == 6) {
if (ret == 5) {
process(arr[1], true);
process(arr[3], true);
process(arr[5], true);
} else if (ret == 4) {
process(arr[1], true);
process(arr[3], true);
process(arr[5], false);
} else if (ret == 3) {
process(arr[5], true);
vector<int> nArr = {a[1], arr[1], a[0], b[0], arr[3], b[1]};
nextPos(v, pos);
if (pos < (int) v.size()) {
nArr.push_back(v[pos]), ++pos;
nArr.push_back(b[2]);
}
nextPos(v, pos);
if (pos < (int) v.size()) {
nArr.push_back(v[pos]), ++pos;
}
int cur = use_machine(nArr) - 1;
process(arr[1], !(cur & 4));
process(arr[3], (cur & 4));
process(nArr[6], (cur & 2));
process(nArr[8], (cur & 1));
} else if (ret == 2) {
process(arr[5], false);
vector<int> nArr = {a[1], arr[1], a[0], b[0], arr[3], b[1]};
nextPos(v, pos);
if (pos < (int) v.size()) {
nArr.push_back(v[pos]), ++pos;
nArr.push_back(b[2]);
}
nextPos(v, pos);
if (pos < (int) v.size()) {
nArr.push_back(v[pos]), ++pos;
}
int cur = use_machine(nArr) - 1;
process(arr[1], !(cur & 4));
process(arr[3], (cur & 4));
process(nArr[6], (cur & 2));
process(nArr[8], (cur & 1));
} else if (ret == 1) {
process(arr[1], false);
process(arr[3], false);
process(arr[5], true);
} else {
process(arr[1], false);
process(arr[3], false);
process(arr[5], false);
}
}
} else if (a.size() > 1) {
vector<int> arr;
nextPos(v, pos);
if (pos < (int) v.size()) {
arr.push_back(v[pos]), ++pos;
arr.push_back(a[0]);
}
nextPos(v, pos);
if (pos < (int) v.size()) {
arr.push_back(v[pos]), ++pos;
arr.push_back(a[1]);
}
int ret = use_machine(arr);
if (arr.size() == 2) {
if (ret == 1) {
process(arr[0], false);
} else {
process(arr[0], true);
}
exit(-1);
} else if (arr.size() == 4) {
if (ret == 3) {
process(arr[0], false);
process(arr[2], false);
} else if (ret == 2) {
process(arr[0], true);
process(arr[2], false);
} else if (ret == 1) {
process(arr[0], false);
process(arr[2], true);
} else {
process(arr[0], true);
process(arr[2], true);
}
}
} else if (b.size() > 1) {
vector<int> arr;
nextPos(v, pos);
if (pos < (int) v.size()) {
arr.push_back(v[pos]), ++pos;
arr.push_back(b[0]);
}
nextPos(v, pos);
if (pos < (int) v.size()) {
arr.push_back(v[pos]), ++pos;
arr.push_back(b[1]);
}
int ret = use_machine(arr);
if (arr.size() == 2) {
if (ret == 1) {
process(arr[0], true);
} else {
process(arr[0], false);
}
exit(-1);
} else if (arr.size() == 4) {
if (ret == 3) {
process(arr[0], true);
process(arr[2], true);
} else if (ret == 2) {
process(arr[0], false);
process(arr[2], true);
} else if (ret == 1) {
process(arr[0], true);
process(arr[2], false);
} else {
process(arr[0], false);
process(arr[2], false);
}
}
} else {
vector<int> arr = {a[0]};
nextPos(v, pos);
if (pos < (int) v.size()) arr.push_back(v[pos]), ++pos;
else break;
int ret = use_machine(arr);
if (ret & 1) {
process(arr[1], false);
} else {
process(arr[1], true);
}
}
}
ans = a.size();
for (int x : missing) {
if (!found.count(x))
v.push_back(x);
}
if (a.size() >= b.size()) {
while (pos < (int) v.size()) {
vector<int> arr;
int used = 0;
for (int i = 0; i < (int) a.size(); ++i) {
arr.push_back(a[i]);
nextPos(v, pos);
if (pos < (int) v.size()) {
arr.push_back(v[pos]), ++pos;
++used;
} else break;
}
int ret = use_machine(arr);
int diff = (ret / 2) + (ret & 1);
ans += used - diff;
if (ret & 1) {
b.push_back(arr.back());
} else {
a.push_back(arr.back());
}
}
} else {
while (pos < (int) v.size()) {
vector<int> arr;
int used = 0;
for (int i = 0; i < (int) b.size(); ++i) {
arr.push_back(b[i]);
nextPos(v, pos);
if (pos < (int) v.size()) {
arr.push_back(v[pos]), ++pos;
++used;
} else break;
}
int ret = use_machine(arr);
int diff = (ret / 2) + (ret & 1);
ans += diff;
if (ret & 1) {
a.push_back(arr.back());
} else {
b.push_back(arr.back());
}
}
}
return ans;
}
// int count_mushrooms(int n) {
// int ans = 1;
// for (int i = 1; i < n; i += 2) {
// vector<int> v;
// if (i + 1 < n) v = {i, 0, i + 1};
// else v = {i, 0};
// int ret = use_machine(v);
// ans += (v.size() - 1) - ret;
// }
// return ans;
// }
// int main() {
// ios::sync_with_stdio(false);
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
256 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
8 ms |
512 KB |
Output is correct |
| 8 |
Correct |
7 ms |
512 KB |
Output is correct |
| 9 |
Correct |
7 ms |
512 KB |
Output is correct |
| 10 |
Correct |
7 ms |
512 KB |
Output is correct |
| 11 |
Correct |
7 ms |
512 KB |
Output is correct |
| 12 |
Correct |
7 ms |
512 KB |
Output is correct |
| 13 |
Correct |
7 ms |
512 KB |
Output is correct |
| 14 |
Correct |
4 ms |
512 KB |
Output is correct |
| 15 |
Correct |
10 ms |
512 KB |
Output is correct |
| 16 |
Correct |
7 ms |
512 KB |
Output is correct |
| 17 |
Correct |
4 ms |
384 KB |
Output is correct |
| 18 |
Correct |
7 ms |
512 KB |
Output is correct |
| 19 |
Correct |
7 ms |
512 KB |
Output is correct |
| 20 |
Correct |
7 ms |
512 KB |
Output is correct |
| 21 |
Correct |
7 ms |
512 KB |
Output is correct |
| 22 |
Correct |
10 ms |
512 KB |
Output is correct |
| 23 |
Correct |
7 ms |
512 KB |
Output is correct |
| 24 |
Correct |
5 ms |
384 KB |
Output is correct |
| 25 |
Correct |
7 ms |
512 KB |
Output is correct |
| 26 |
Correct |
8 ms |
512 KB |
Output is correct |
| 27 |
Correct |
7 ms |
512 KB |
Output is correct |
| 28 |
Correct |
7 ms |
512 KB |
Output is correct |
| 29 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 30 |
Correct |
6 ms |
512 KB |
Output is correct |
| 31 |
Correct |
8 ms |
512 KB |
Output is correct |
| 32 |
Correct |
7 ms |
512 KB |
Output is correct |
| 33 |
Correct |
7 ms |
512 KB |
Output is correct |
| 34 |
Correct |
8 ms |
512 KB |
Output is correct |
| 35 |
Correct |
8 ms |
512 KB |
Output is correct |
| 36 |
Correct |
8 ms |
512 KB |
Output is correct |
| 37 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 38 |
Correct |
7 ms |
512 KB |
Output is correct |
| 39 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 40 |
Correct |
9 ms |
512 KB |
Output is correct |
| 41 |
Correct |
8 ms |
512 KB |
Output is correct |
| 42 |
Correct |
11 ms |
512 KB |
Output is correct |
| 43 |
Correct |
8 ms |
512 KB |
Output is correct |
| 44 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 45 |
Correct |
10 ms |
512 KB |
Output is correct |
| 46 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 47 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 48 |
Correct |
7 ms |
512 KB |
Output is correct |
| 49 |
Partially correct |
9 ms |
512 KB |
Output is partially correct |
| 50 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 51 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 52 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 53 |
Correct |
10 ms |
512 KB |
Output is correct |
| 54 |
Correct |
10 ms |
512 KB |
Output is correct |
| 55 |
Partially correct |
10 ms |
512 KB |
Output is partially correct |
| 56 |
Correct |
10 ms |
512 KB |
Output is correct |
| 57 |
Correct |
10 ms |
512 KB |
Output is correct |
| 58 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 59 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 60 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 61 |
Partially correct |
8 ms |
512 KB |
Output is partially correct |
| 62 |
Correct |
0 ms |
256 KB |
Output is correct |
| 63 |
Correct |
0 ms |
256 KB |
Output is correct |
| 64 |
Correct |
0 ms |
256 KB |
Output is correct |
| 65 |
Correct |
0 ms |
256 KB |
Output is correct |
| 66 |
Correct |
0 ms |
256 KB |
Output is correct |
| 67 |
Correct |
0 ms |
256 KB |
Output is correct |
| 68 |
Correct |
0 ms |
256 KB |
Output is correct |
| 69 |
Correct |
0 ms |
256 KB |
Output is correct |
| 70 |
Correct |
0 ms |
256 KB |
Output is correct |
| 71 |
Correct |
0 ms |
256 KB |
Output is correct |
| 72 |
Correct |
0 ms |
256 KB |
Output is correct |
| 73 |
Correct |
0 ms |
256 KB |
Output is correct |
| 74 |
Correct |
0 ms |
256 KB |
Output is correct |
| 75 |
Correct |
0 ms |
256 KB |
Output is correct |
| 76 |
Correct |
0 ms |
256 KB |
Output is correct |
| 77 |
Correct |
0 ms |
256 KB |
Output is correct |
| 78 |
Correct |
0 ms |
256 KB |
Output is correct |
| 79 |
Correct |
0 ms |
256 KB |
Output is correct |
| 80 |
Correct |
1 ms |
256 KB |
Output is correct |
| 81 |
Correct |
0 ms |
256 KB |
Output is correct |
| 82 |
Correct |
1 ms |
256 KB |
Output is correct |
| 83 |
Correct |
1 ms |
256 KB |
Output is correct |
| 84 |
Correct |
0 ms |
256 KB |
Output is correct |
| 85 |
Correct |
1 ms |
256 KB |
Output is correct |
| 86 |
Correct |
0 ms |
256 KB |
Output is correct |
| 87 |
Correct |
0 ms |
256 KB |
Output is correct |
| 88 |
Correct |
0 ms |
256 KB |
Output is correct |
| 89 |
Correct |
0 ms |
256 KB |
Output is correct |
| 90 |
Correct |
1 ms |
256 KB |
Output is correct |
| 91 |
Correct |
0 ms |
256 KB |
Output is correct |
