# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
439948 | dacin21 | Dungeons Game (IOI21_dungeons) | C++17 | 7034 ms | 102108 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 "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
const int BLOCK = 5000;
const int MAX_SKILL = 1.01e7;
const int U = 10;
const int inf = 1e9;
int n;
struct Link{
int to;
int gain;
};
struct Node{
Link win, loss;
int thresh;
};
struct Jump{
int to;
int max_valid;
ll gain;
};
vector<ll> win_gain;
vector<Node> g;
vector<vector<Jump> > jumps;
void init(int n_, vector<int> s, vector<int> p, vector<int> w, vector<int> l){
n = n_;
g.assign(n+1, Node{});
for(int i=0; i<n; ++i){
g[i] = Node{Link{w[i], s[i]}, Link{l[i], p[i]}, s[i]};
}
g[n] = Node{Link{n, 0}, Link{n, 0}, 0};
// compute win once we hit 1e7
win_gain.assign(n+1, 0);
for(int i=n-1; i>=0; --i){
win_gain[i] = win_gain[g[i].win.to] + g[i].win.gain;
}
// assume we take BLOCK steps
// then build jump table
jumps.resize(U+1, vector<Jump>(n+1));
for(int i=0; i<=n; ++i){
if(g[i].thresh <= BLOCK){
jumps[0][i] = Jump{g[i].win.to, inf, g[i].win.gain};
} else {
jumps[0][i] = Jump{g[i].loss.to, g[i].thresh-1, g[i].loss.gain};
}
}
for(int i=1; i<=U; ++i){
for(int j=0; j<=n; ++j){
auto &e = jumps[i-1][j];
const int k = e.to;
auto const&f = jumps[i-1][k];
jumps[i][j] = Jump{f.to, max<ll>(-1, min<ll>(e.max_valid, f.max_valid-e.gain)), e.gain+f.gain};
}
}
}
long long simulate(int x, int z) {
int u = x;
ll s = z;
auto do_single_step = [&](){
if(s >= g[u].thresh){
s += g[u].win.gain;
u = g[u].win.to;
} else {
s += g[u].loss.gain;
u = g[u].loss.to;
}
};
for(int it=0; it<BLOCK; ++it){
do_single_step();
}
assert(u == n || s >= BLOCK);
while(u != n && s < MAX_SKILL){
int i = 0;
while(i >= 0){
auto &e = jumps[i][u];
if(s < e.max_valid){
s += e.gain;
u = e.to;
i = min(i+1, U);
} else --i;
}
do_single_step();
}
s += win_gain[u];
return s;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |