# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
828698 | Minindu206 | Counting Mushrooms (IOI20_mushrooms) | C++14 | 1 ms | 208 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> posa, posb, pos;
int acnt = 1, bcnt = 0, cnt, ans = 1;
posa.push_back(0);
if (n <= 170)
{
for (int i = 1; i < min(170, n); i++)
{
int cur = use_machine({0, i});
if (cur == 0)
ans++;
}
return ans;
}
if (use_machine({0, 1}))
posb.push_back(1), acnt++, ans++;
else
posa.push_back(1), bcnt++;
if (use_machine({0, 2}))
posb.push_back(2), acnt++, ans++;
else
posa.push_back(2), bcnt++;
int c = 0;
if (acnt >= bcnt)
pos = posa, c = 1;
else
pos = posb;
for (int i = 3; i < 171; i += 2)
{
int cur = use_machine({pos[0], i, pos[1], i + 1});
if (c)
ans += (cur - ((cur + 1) / 2));
else
ans += (cur + 1) / 2;
if (c)
{
if (cur == 1)
{
posb.push_back(i + 1);
posa.push_back(i);
acnt++, bcnt++;
}
else if (cur == 2)
{
posb.push_back(i);
posa.push_back(i + 1);
acnt++, bcnt++;
}
else if (cur == 3)
{
posb.push_back(i);
posb.push_back(i + 1);
bcnt += 2;
}
else
{
posa.push_back(i);
posa.push_back(i + 1);
acnt += 2;
}
}
else
{
if (cur == 2)
{
posb.push_back(i + 1);
posa.push_back(i);
acnt++, bcnt++;
}
else if (cur == 1)
{
posb.push_back(i);
posa.push_back(i + 1);
acnt++, bcnt++;
}
else if (cur == 0)
{
posb.push_back(i);
posb.push_back(i + 1);
bcnt += 2;
}
else
{
posa.push_back(i);
posa.push_back(i + 1);
acnt += 2;
}
}
}
if (acnt >= bcnt)
pos = posa;
else
pos = posb;
int i = 171;
vector<int> chk;
while (i < n)
{
chk.clear();
int cur = 0, vr = i + pos.size();
for (; i < min(vr, n) && cur < pos.size(); i++)
{
chk.push_back(i);
chk.push_back(pos[cur]);
cur++;
}
int ncur = use_machine(chk);
if (acnt >= bcnt)
ans += (cur - ((ncur + 1) / 2));
else
ans += (ncur + 1) / 2;
}
return n - ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |