# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
834798 | Johann | 버섯 세기 (IOI20_mushrooms) | C++14 | 8 ms | 336 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "mushrooms.h"
#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
int count_mushrooms(int n)
{
vi m;
// 0 for a and 1 for b
vvi sure(2);
vi cnt(2, 0);
sure[0].push_back(0);
cnt[0] = 1;
int idx = 1;
while (idx < n && max(sz(sure[0]), sz(sure[1])) < 2)
{
assert(sz(sure[0]) > 0);
m.clear();
m.push_back(sure[0].front());
m.push_back(idx++);
int c1 = use_machine(m);
++cnt[c1], sure[c1].push_back(m.back());
}
while (idx < n && max(sz(sure[0]), sz(sure[1])) < sqrt(n) + 10)
{
int i = (sz(sure[0]) < sz(sure[1]));
m.clear();
for (int j = 0; j < 2; ++j)
{
m.push_back(sure[i][j]);
if (idx < n)
m.push_back(idx++);
}
int c2 = use_machine(m);
++cnt[i ^ (c2 / 2)], sure[i ^ (c2 / 2)].push_back(m[1]);
if (sz(m) > 3)
++cnt[i ^ (c2 & 1)], sure[i ^ (c2 & 1)].push_back(m[3]);
}
while (idx < n)
{
int i = (sz(sure[0]) < sz(sure[1]));
m.clear();
for (int j = 0; j < sz(sure[i]) && idx < n; ++j)
{
m.push_back(sure[i][j]);
m.push_back(idx++);
}
int c3 = use_machine(m);
int lenCnt = (sz(m) - 2) / 2;
cnt[i] += lenCnt - (c3 / 2);
cnt[i ^ 1] += c3 / 2;
++cnt[i ^ (c3 & 1)], sure[i ^ (c3 & 1)].push_back(m.back());
}
return cnt[0];
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |