| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 605022 | SamAnd | 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 "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define m_p make_pair
typedef long long ll;
mt19937 rnf(234);
const int M = 250;
int count_mushrooms(int n)
{
vector<int> v;
for (int i = 1; i < min(n, M); ++i)
v.push_back(i);
vector<int> a;
vector<int> b;
a.push_back(0);
while (!v.empty())
{
if (sz(v) == 1 || (max(sz(a), sz(b)) < 2))
{
int q = use_machine({0, v.back()});
if (q == 0)
a.push_back(v.back());
else
b.push_back(v.back());
v.pop_back();
continue;
}
if (sz(a) >= 2)
{
int q = use_machine({a[0], v[0], a[1], v[1]});
if (q == 0)
{
a.push_back(v[0]);
a.push_back(v[1]);
}
else if (q == 3)
{
b.push_back(v[0]);
b.push_back(v[1]);
}
else if (q == 1)
{
a.push_back(v[0]);
b.push_back(v[1]);
}
else if (q == 2)
{
b.push_back(v[0]);
a.push_back(v[1]);
}
}
else
{
int q = use_machine({b[0], v[0], b[1], v[1]});
if (q == 0)
{
b.push_back(v[0]);
b.push_back(v[1]);
}
else if (q == 3)
{
a.push_back(v[0]);
a.push_back(v[1]);
}
else if (q == 1)
{
b.push_back(v[0]);
a.push_back(v[1]);
}
else if (q == 2)
{
a.push_back(v[0]);
b.push_back(v[1]);
}
}
reverse(all(v));
v.pop_back();
v.pop_back();
}
int ans = sz(a);
for (int i = M; i < n; ++i)
v.push_back(i);
if (sz(a) > sz(b))
{
while (!v.empty())
{
if (sz(v) < sz(a))
{
vector<int> x;
x.push_back(a[0]);
for (int i = 0; i < sz(v); ++i)
{
x.push_back(v[i]);
x.push_back(a[i + 1]);
}
ans += (sz(v) - use_machine(x) / 2);
v.clear();
}
else
{
vector<int> u;
for (int i = 0; i < sz(a) - 1; ++i)
{
u.push_back(v.back());
v.pop_back();
}
vector<int> x;
x.push_back(a[0]);
for (int i = 0; i < sz(u); ++i)
{
x.push_back(u[i]);
x.push_back(a[i + 1]);
}
ans += (sz(u) - use_machine(x) / 2);
u.clear();
}
}
}
else
{
while (!v.empty())
{
if (sz(v) < sz(b))
{
vector<int> x;
x.push_back(b[0]);
for (int i = 0; i < sz(v); ++i)
{
x.push_back(v[i]);
x.push_back(b[i + 1]);
}
ans += use_machine(x) / 2;
v.clear();
}
else
{
vector<int> u;
for (int i = 0; i < sz(b) - 1; ++i)
{
u.push_back(v.back());
v.pop_back();
}
vector<int> x;
x.push_back(b[0]);
for (int i = 0; i < sz(u); ++i)
{
x.push_back(u[i]);
x.push_back(b[i + 1]);
}
ans += use_machine(x) / 2;
u.clear();
}
}
}
return ans;
}