| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1079762 | GusterGoose27 | Dungeons Game (IOI21_dungeons) | C++17 | 0 ms | 0 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;
typedef long long ll;
const int MAXN = 5e4+5;//4e5+5;
const ll MAXS = 1e18;
const int MAXB = 25; // will always terminate after 2^24 steps
vector<int> s, p, w, l;
int n;
struct step {
ll st; ll m, f; // strength_gain, final, min to beat
step() {}
step(int i, int b) { // bucket id
if (i == n) {
st = 0;
f = n;
m = 0;
}
else {
int lcut = (1<<b);
if (lcut >= s[i]) {
st = s[i];
f = w[i];
m = MAXS;
}
else {
st = p[i];
f = l[i];
m = s[i];
}
}
// if (i == 24 && b == 9) cerr << "1 " << m << '\n';
// assert(m != 0);
// assert(f <= n);
}
step(step &a, step &b) {
st = min(MAXS, a.st+b.st);
f = b.f;
m = min(a.m, (int)max(0ll, b.m-a.st));
// assert(f <= n);
}
};
step lift[MAXB][MAXB][MAXN]; // cutoff, lift num, start
void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
n = N;
s = S;
p = P;
w = W;
l = L;
for (int c = 0; c < MAXB; c++) {
for (int i = 0; i <= n; i++) lift[c][0][i] = step(i, c);
// if (c == 9) cerr << lift[9][0][24].m << '\n';
for (int b = 1; b < MAXB; b++) {
for (int i = 0; i <= n; i++) lift[c][b][i] = step(lift[c][b-1][i], lift[c][b-1][lift[c][b-1][i].f]);
}
}
// cerr << lift[9][0][24].m << '\n';
}
ll simulate2(int x, ll z) {
// cerr << x << ' ' << z << '\n';
assert(x <= n);
if (x == n) return z;
int c = (z >= (1ll<<(MAXB-1)) ? MAXB-1 : 31-__builtin_clz(z));
// cerr << c << ' ' << z << '\n';
if (c == MAXB-1) return lift[c][MAXB-1][x].st + z;
for (int b = MAXB-1; b >= 0; b--) {
if (z < lift[c][b][x].m) return simulate2(lift[c][b][x].f, lift[c][b][x].st+z);
}
// if (z < s[x]) return -1;
// if (z < s[x]) {
// cerr << c << ' ' << z << ' ' << n << ' ' << x << '\n';
// cerr << lift[c][0][x].m << ' ' << s[x] << '\n';
// assert(false);
// }
assert(z >= s[x]);
return simulate2(w[x], z + s[x]);
}
ll simulate(int x, int z) {
// cerr << lift[9][0][24].m << '\n';
return simulate2(x, z);
}