# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
654044 | ellakass | 버섯 세기 (IOI20_mushrooms) | C++14 | 9 ms | 316 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include "mushrooms.h"
int count_mushrooms(int n)
{
std::vector < int > V0 = { 0 }, V1;
int a1 = use_machine({ 0, 1 });
if (n == 2)
return 2 - a1;
int unused = 2, Q = 1;
if (a1)
{
V1.push_back(1);
int a2 = use_machine({ 0, 2 });
if (a2)
V1.push_back(2);
else
V0.push_back(2);
unused++;
Q++;
}
else
V0.push_back(1);
while (Q < 82 && std::min(V0.size(), V1.size()) < 3)
{
if (unused == n)
return V0.size();
if (unused == n - 1)
return V0.size() + 1 - use_machine({ 0, n - 1 });
if (V0.size() >= 2)
{
int r = use_machine({ V0[0], unused, V0[1], unused + 1 });
if (r & 2)
V1.push_back(unused);
else
V0.push_back(unused);
if (r & 1)
V1.push_back(unused + 1);
else
V0.push_back(unused + 1);
unused += 2;
}
else
{
int r = use_machine({ V1[0], unused, V1[1], unused + 1 });
if (r & 2)
V0.push_back(unused);
else
V1.push_back(unused);
if (r & 1)
V0.push_back(unused + 1);
else
V1.push_back(unused + 1);
unused += 2;
}
Q++;
}
int op0 = -1, op1 = -1;
while (Q < 82)
{
if (op0 == -1)
{
if (unused == n)
return V0.size();
if (unused == n - 1)
return V0.size() + 1 - use_machine({ 0, n - 1 });
if (unused == n - 2)
{
int r = use_machine({ V0[0], unused, V0[1], unused + 1 });
return V0.size() + !(r & 2) + !(r & 1);
}
int r = use_machine({ V0[0], unused, V0[1], unused + 1, V0[2], unused + 2 });
if (r & 1)
V1.push_back(unused + 2);
else
V0.push_back(unused + 2);
r >>= 1;
if (r == 1)
{
op0 = unused;
op1 = unused + 1;
}
else if (r == 0)
{
V0.push_back(unused);
V0.push_back(unused + 1);
}
else
{
V1.push_back(unused);
V1.push_back(unused + 1);
}
unused += 3;
}
else
{
if (unused == n)
return V0.size() + 1;
if (unused == n - 1)
return V0.size() + 2 - use_machine({ 0, n - 1 });
int r = use_machine({ unused, V0[0], unused + 1, V0[1], op0, V0[2], V1[0], op1, V1[1] }) - 1;
if (r & 1)
V1.push_back(unused);
else
V0.push_back(unused);
if (r & 2)
V1.push_back(unused + 1);
else
V0.push_back(unused + 1);
if (r & 4)
{
V1.push_back(op0);
V0.push_back(op1);
}
else
{
V0.push_back(op0);
V1.push_back(op1);
}
op0 = op1 = -1;
unused += 2;
}
Q++;
}
int O = V0.size() + (op0 != -1);
while (true)
{
std::vector < int > query;
if (V0.size() >= V1.size())
{
if (n - unused > V0.size())
{
for (int i = 0; i < V0.size(); i++)
{
query.push_back(V0[i]);
query.push_back(unused + i);
}
int r = use_machine(query);
O += V0.size() - (r + 1 >> 1);
unused += V0.size();
if (r & 1)
V1.push_back(unused - 1);
else
V0.push_back(unused - 1);
}
else
{
int L = n - unused;
for (int i = 0; i < L; i++)
{
query.push_back(V0[i]);
query.push_back(unused + i);
}
return O + L - (use_machine(query) + 1 >> 1);
}
}
else
{
if (n - unused > V1.size())
{
for (int i = 0; i < V1.size(); i++)
{
query.push_back(V1[i]);
query.push_back(unused + i);
}
int r = use_machine(query);
O += r + 1 >> 1;
unused += V1.size();
if (r & 1)
V0.push_back(unused - 1);
else
V1.push_back(unused - 1);
}
else
{
int L = n - unused;
for (int i = 0; i < L; i++)
{
query.push_back(V1[i]);
query.push_back(unused + i);
}
return O + (use_machine(query) + 1 >> 1);
}
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |