#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
int count_mushrooms(int n) {
int ans = 0, m = min(100, n);
if (n <= 400) {
for (int i = 1; i+1 < n; i += 2) {
ans += use_machine({i, 0, i+1});
}
if (n % 2 == 0) {
ans += use_machine({0, n-1});
}
return n-ans;
}
int as = 0, bs = 0;
vector<int> a, b, st;
a.push_back(0);
if (use_machine({0, 1})) {
b.push_back(1);
} else {
a.push_back(1);
}
if (use_machine({0, 2})) {
b.push_back(2);
} else {
a.push_back(2);
}
if (b.size() == 2) {
swap(a, b);
}
for (int i = n-1; i >= 0; i--) {
st.push_back(i);
}
for (int i = 0; i < m; i++) {
int f1 = st.back(), f2;
st.pop_back();
f2 = st.back();
st.pop_back();
int v = use_machine({f1, a[0], f2, a[1]});
if (v == 0) {
a.push_back(f1);
a.push_back(f2);
} else if (v == 1) {
b.push_back(f1);
a.push_back(f2);
} else if (v == 2) {
a.push_back(f1);
b.push_back(f2);
} else {
b.push_back(f1);
b.push_back(f2);
}
}
if (b.size() > a.size()) {
swap(a, b);
}
as = a.size();
bs = b.size();
while(!st.empty()) {
int va = 0, vb = 0, vn = 0, v;
vector<int> query;
for (int i = 0; i < a.size() && !st.empty(); i++) {
query.push_back(st.back());
st.pop_back();
query.push_back(a[i]);
vn++;
}
v = use_machine(query);
vb = (v+1)/2;
va = vn-vb;
as += va;
bs += vb;
if (v & 1) {
b.push_back(query[0]);
} else {
a.push_back(query[0]);
}
if (b.size() > a.size()) {
swap(as, bs);
swap(a, b);
}
}
if (count(b.begin(), b.end(), 0)) {
swap(as, bs);
}
return as;
}
Compilation message
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:62:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int i = 0; i < a.size() && !st.empty(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
344 KB |
Duplicate value 1 in the query array. |
| 7 |
Halted |
0 ms |
0 KB |
- |
