# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1117321 | pokmui9909 | Counting Mushrooms (IOI20_mushrooms) | C++17 | 9 ms | 856 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, 120), S = 1;
vector<ll> P, Q;
P.push_back(0);
while(S < N && P.size() < B && Q.size() < B){
if(S + 1 < N && 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);
}
S += 2;
} else if(S + 1 < N && Q.size() >= 2){
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;
} else {
ll f = use_machine((vector<int>){0, S});
if(f == 0){
P.push_back(S);
} else {
Q.push_back(S);
}
S++;
}
}
ll Ans = P.size();
for(ll i = S; i < N; i += B){
B = max(P.size(), Q.size());
vector<int> V;
if(P.size() == B){
for(ll j = 0; j < B; j++){
if(i + j >= N) break;
V.push_back(P[j]);
V.push_back(i + j);
Ans++;
}
ll t = use_machine(V);
Ans -= (t / 2) + (t % 2);
if(t % 2 == 0){
P.push_back(V.back());
} else {
Q.push_back(V.back());
}
} else {
for(ll j = 0; j < B; j++){
if(i + j >= N) break;
V.push_back(Q[j]);
V.push_back(i + j);
}
ll t = use_machine(V);
Ans += (t / 2) + (t % 2);
if(t % 2 == 1){
P.push_back(V.back());
} else {
Q.push_back(V.back());
}
}
}
return Ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |