#include <math.h>
#include "mushrooms.h"
int count_mushrooms(int n) {
std::vector<int> m;
int ans = 1;
if (n <= 226) {
for (int i = 1; i < n; i++) {
m = {0, i};
int res = use_machine(m);
if (res == 0) ans++;
}
return ans;
}
int k = (int) (sqrt(n / 2));
// 0, 1, ..., k
// 0, k + 1, ..., 2k
// 0, 2k + 1, ..., 3k
// 0, 3k + 1, ..., 4k
//...
// bk + 1 <= n - 1
int B = (n - 2) / k;
// 0 ... B
std::vector<int> answers;
std::vector<int> ones, zeroes;
int known[20001];
for (int q = 0; q <= B; q++) {
std::vector<int> query;
query.push_back(0);
int largest = 0;
for (int i = 1; i <= k; i++) {
int num = i + q * k;
if (num >= n) break;
largest = num;
query.push_back(num);
}
int res = use_machine(m);
answers.push_back(res);
if (res == 0) {
zeroes.push_back(largest);
} else {
ones.push_back(largest);
}
known[largest] = 1;
}
int countZeroes = 1 + zeroes.size();
std::vector<int> unknown;
for (int i = 1; i < n; i++) {
if (known[i] != 1) {
unknown.push_back(i);
}
}
std::vector<int> indices = (ones.size() > zeroes.size() ? ones : zeroes);
bool isOne = ones.size() > zeroes.size();
int s = indices.size();
for (int i = 0; i < unknown.size(); i++) {
std::vector<int> query;
query.push_back(indices[0]);
for (int j = 1; j < s && i + j - 1 < unknown.size(); j++) {
query.push_back(unknown[i + j - 1]);
query.push_back(indices[j]);
}
int res = use_machine(query);
if (isOne) {
int ones = res / 2;
countZeroes += s - 1 - ones;
} else {
countZeroes += res / 2;
}
i = i + s - 2;
}
return countZeroes;
}
Compilation message
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i = 0; i < unknown.size(); i++) {
| ~~^~~~~~~~~~~~~~~~
mushrooms.cpp:59:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int j = 1; j < s && i + j - 1 < unknown.size(); j++) {
| ~~~~~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
256 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
0 ms |
256 KB |
Output is correct |
| 4 |
Correct |
1 ms |
256 KB |
Output is correct |
| 5 |
Correct |
2 ms |
256 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
256 KB |
Too small array for query. |
| 7 |
Halted |
0 ms |
0 KB |
- |
