Submission #598313

#	Time	Username	Problem	Language	Result	Execution time	Memory
598313		KoD	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2858 ms	2061128 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>

using ll = long long;
using std::vector;

struct dungeon {
    int s, p, w, l;
};

struct info {
    int pos, thres;
    ll sum;
    info() = default;
};

constexpr int LOG = 24;
int size;
vector<dungeon> data;
vector<info> lift[LOG][LOG];
vector<info> win_all[LOG];

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    size = n;
    data.reserve(n);
    for (int i = 0; i < n; ++i) {
        data.push_back({s[i], p[i], w[i], l[i]});
    }
    for (int stage = 0; stage < LOG; ++stage) {
        lift[stage][0].resize(n + 1);
        const int lb = 1 << stage;
        const int ub = 1 << (stage + 1);
        for (int i = 0; i < n; ++i) {
            if (s[i] < lb) {
                lift[stage][0][i] = {w[i], std::max(0, ub - s[i]), s[i]};
            } else if (s[i] >= ub) {
                lift[stage][0][i] = {l[i], std::max(0, ub - p[i]), p[i]};
            } else {
                lift[stage][0][i] = {l[i], std::max(0, std::min(s[i], ub - p[i])), p[i]};
            }
        }
        lift[stage][0][n] = {n, 0, 0};
        for (int k = 0; k < stage; ++k) {
            lift[stage][k + 1].resize(n + 1);
            for (int i = 0; i <= n; ++i) {
                const auto [p0, t0, s0] = lift[stage][k][i];
                const auto [p1, t1, s1] = lift[stage][k][p0];
                lift[stage][k + 1][i] = {p1, s0 >= t1 ? 0 : std::min<int>(t0, t1 - s0), s0 + s1};
            }
        }
    }
    win_all[0].resize(n + 1);
    for (int i = 0; i < n; ++i) {
        win_all[0][i] = {w[i], 0, s[i]};
    }
    win_all[0][n] = {n, 0, 0};
    for (int k = 0; k < LOG - 1; ++k) {
        win_all[k + 1].resize(n + 1);
        for (int i = 0; i <= n; ++i) {
            const auto [p0, t0, s0] = win_all[k][i];
            const auto [p1, t1, s1] = win_all[k][p0];
            win_all[k + 1][i] = {p1, 0, s0 + s1};
        }
    }
}

ll simulate(int x, int z) {
    int stage = 0;
    while (true) {
        while (z >= (1 << (stage + 1))) {
            stage += 1;
        }
        if (x == size) {
            return z;
        }
        if (stage >= LOG) {
            break;
        }
        for (int k = stage; k >= 0; --k) {
            if (lift[stage][k][x].pos != size and z < lift[stage][k][x].thres) {
                z += lift[stage][k][x].sum;
                x = lift[stage][k][x].pos;
            }
        }
        if (z >= data[x].s) {
            z += data[x].s;
            x = data[x].w;
        } else {
            z += data[x].p;
            x = data[x].l;
        }
    }
    ll ret = z;
    for (int k = LOG - 1; k >= 0; --k) {
        if (win_all[k][x].pos != size) {
            ret += win_all[k][x].sum;
            x = win_all[k][x].pos;
        }
    }
    ret += data[x].s;
    return ret;
}

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11