| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1117302 | pokmui9909 | Counting Mushrooms (IOI20_mushrooms) | C++17 | 3 ms | 336 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;
using ll = long long;
#define x first
#define y second
int count_mushrooms(int N){
ll B = min(N, 141), S = 1;
vector<ll> P, Q;
P.push_back(0);
ll F = 0;
while(S < N && P.size() < 2 && Q.size() < 2){
ll f = use_machine((vector<int>){0, S});
if(f == 0){
P.push_back(S);
} else {
Q.push_back(S);
}
S++;
F += 2;
}
while(S < N && P.size() < B && Q.size() < B){
if(S + 1 < N){
if(P.size() >= 2){
ll f = use_machine((vector<int>){P[0], S, P[1], S + 1});
if(f / 2 == 0){
P.push_back(S);
} else {
Q.push_back(S);
}
if(f % 2 == 0){
P.push_back(S + 1);
} else {
Q.push_back(S + 1);
}
} else {
ll f = use_machine((vector<int>){Q[0], S, Q[1], S + 1});
if(f / 2 == 1){
P.push_back(S);
} else {
Q.push_back(S);
}
if(f % 2 == 1){
P.push_back(S + 1);
} else {
Q.push_back(S + 1);
}
}
S += 2;
F += 4;
} else {
ll f = use_machine((vector<int>){0, S});
if(f == 0){
P.push_back(S);
} else {
Q.push_back(S);
}
S++;
F += 2;
}
}
B = max(P.size(), Q.size());
ll Rev = 0;
if(Q.size() == B){
Rev = 1;
swap(P, Q);
}
ll Ans = P.size();
for(ll i = S; i < N; i += B){
vector<int> V;
for(ll j = 0; j < B; j++){
if(i + j >= N) break;
if(j % 2 == 0) V.push_back(P[j]);
V.push_back(i + j);
Ans++;
}
ll t = use_machine(V);
Ans -= (t / 2) + (t % 2);
F += V.size();
}
assert(F <= 100000);
return (Rev == 0 ? Ans : N - Ans);
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||