| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 419728 | KoD | Packing Biscuits (IOI20_biscuits) | C++17 | 0 ms | 0 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 <bits/stdc++.h>
#include "mushrooms.h"
template <class T> using Vec = std::vector<T>;
constexpr int NAIVE = 20;
int count_mushrooms(int n) {
if (n <= 227) {
int ret = 1;
for (int i = 1; i < n; ++i) {
ret += 1 - use_machine(Vec<int>{0, i});
}
return ret;
}
Vec<int> a, b;
a.push_back(0);
(use_machine(Vec<int>{0, 1}) ? b : a).push_back(1);
(use_machine(Vec<int>{0, 2}) ? b : a).push_back(2);
int seen = 3;
if ((int) a.size() == 2) {
while ((int) std::max(a.size(), b.size()) < NAIVE) {
Vec<int> ask;
ask.push_back(seen);
ask.push_back(a[0]);
ask.push_back(seen + 1);
ask.push_back(a[1]);
const auto rsp = use_machine(ask);
for (int k = 0; k < 2; ++k) {
((rsp >> k & 1) ? b : a).push_back(seen + k);
}
seen += 2;
}
} else {
while ((int) std::max(a.size(), b.size()) < NAIVE) {
Vec<int> ask;
ask.push_back(seen);
ask.push_back(b[0]);
ask.push_back(seen + 1);
ask.push_back(b[1]);
const auto rsp = use_machine(ask);
for (int k = 0; k < 2; ++k) {
((rsp >> k & 1) ? a : b).push_back(seen + k);
}
seen += 2;
}
}
int ret = (int) a.size();
while (seen < n) {
if (a.size() > b.size()) {
Vec<int> ask;
for (int i = 0; i < (int) a.size() and seen < n; ++i) {
ask.push_back(a[i]);
ask.push_back(seen++);
}
const auto rsp = use_machine(ask);
ret += (int) ask.size() / 2;
ret -= (rsp + 1) / 2;
(rsp % 2 == 0 ? a : b).push_back(ask.back());
} else {
Vec<int> ask;
for (int i = 0; i < (int) b.size() and seen < n; ++i) {
ask.push_back(b[i]);
ask.push_back(seen++);
}
const auto rsp = use_machine(ask);
ret += (rsp + 1) / 2;
(rsp % 2 == 0 ? b : a).push_back(ask.back());
}
}
return ret;
}