# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
398400 | kevinxiehk | Counting Mushrooms (IOI20_mushrooms) | C++17 | 14 ms | 312 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "mushrooms.h"
#include "bits/stdc++.h"
using namespace std;
int count_mushrooms(int n) {
vector<int> m;
vector<int> a, b;
int id = 1;
a.emplace_back(0);
while(max(a.size(), b.size()) <= min(100, (int)sqrt(n)) && id < n) {
int t = use_machine({0, id});
if(t == 1) {
b.emplace_back(id);
}
else a.emplace_back(id);
id++;
}
int ans = a.size();
if(a.size() > b.size()) {
for(int i = id; i < n; i += a.size() - 1) {
int l = i, r = min(n - 1, (int)(i + a.size() - 2));
m.clear();
m.emplace_back(a[0]);
for(int j = l; j <= r; j++) {
m.emplace_back(j);
m.emplace_back(a[j - l + 1]);
}
int t = use_machine(m);
ans += (r - l + 1) - (t / 2);
}
}
else {
for(int i = id; i < n; i += b.size() - 1) {
int l = i, r = min(n - 1, (int)(i + b.size() - 2));
m.clear();
m.emplace_back(b[0]);
for(int j = l; j <= r; j++) {
m.emplace_back(j);
m.emplace_back(b[j - l + 1]);
}
int t = use_machine(m);
ans += (t / 2);
}
}
return ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |