oj.uz

Submission #815616

# Submission time Handle Problem Language Result Execution time Memory
815616 2023-08-08T17:27:50 Z skittles1412 Dungeons Game (IOI21_dungeons) C++17
100 / 100
 5808 ms 1728764 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

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

struct DS1 {
    struct Lift {
        int mn_esc, lose_d;
        long add;
    };

    static constexpr int LOGN = 30, BSIZE = 4;

    int n, kv;
    vector<Lift> lift[LOGN];

    DS1() {}
    void build(int _kv, const vector<Dungeon>& arr) {
        n = sz(arr);
        kv = _kv;

        for (auto& a : lift) {
            a.resize(n + 1);
        }

        int up_bound = kv == -1 ? 0 : 1 << (kv + 1);
        for (int i = 0; i < n; i++) {
            auto& [s, p, w, l] = arr[i];

            if (__lg(s) < kv || kv == -1) {
                lift[0][i] = {w == n ? 0 : max(0, up_bound - s), w, s};
                continue;
            } else if (__lg(s) > kv) {
                lift[0][i] = {l == n ? 0 : max(0, up_bound - p), l, p};
                continue;
            }

            lift[0][i] = {l == n ? 0 : max(0, min(s, up_bound - p)), l, p};
        }

        lift[0][n] = {0, n, 0};

        for (int it = 1; it < LOGN; it++) {
            for (int i = 0; i <= n; i++) {
                auto& ql = lift[it - 1][i];
                auto& qr = lift[it - 1][ql.lose_d];

                lift[it][i] = {
                    int(max(long(0), min(long(ql.mn_esc), qr.mn_esc - ql.add))),
                    qr.lose_d, ql.add + qr.add};
            }

            if (it % BSIZE == 0) {
                for (int i = it - BSIZE + 1; i < it; i++) {
                    lift[i].clear();
                    lift[i].shrink_to_fit();
                }
            }
        }
        for (int i = 0; i < LOGN; i++) {
            if (i % BSIZE) {
                lift[i].clear();
                lift[i].shrink_to_fit();
            }
        }
    }

    void advance(int& u, long& w, const vector<Dungeon>& arr) {
        if (u == n || (kv != -1 && __lg(w) > kv)) {
            return;
        }
        // assert(__lg(w) == kv);

        for (int it = LOGN - 1; it >= 0; it--) {
            if (!sz(lift[it])) {
                continue;
            }

            while (u != n) {
                auto& cq = lift[it][u];

                if (kv != -1 && w >= cq.mn_esc) {
                    break;
                }

                u = cq.lose_d;
                w += cq.add;
                dbg(it, u, w);
            }
        }

        if (kv == -1) {
            assert(u == n);
            return;
        }

        dbg(kv, u, w);
        // assert(u != n && __lg(w) == kv);

        dbg(u, arr[u].s, arr[u].p);
        if (w >= arr[u].s) {
            w += arr[u].s;
            u = arr[u].w;
        } else {
            w += arr[u].p;
            u = arr[u].l;
        }

        // auto& cq = lift[0][u];

        // u = cq.win_d;
        // w += cq.win_add;

        dbg(u, w);
        // assert(u == n || __lg(w) > kv);
    }
};

struct Solver {
    static constexpr int LOGN = 30;

    int n;
    vector<Dungeon> arr;
    DS1 lift[LOGN], lift_last;

    Solver() {}
    void build(const vector<Dungeon>& _arr) {
        arr = _arr;
        n = sz(arr);

        for (int i = 0; i < LOGN; i++) {
            lift[i].build(i, arr);
        }
        lift_last.build(-1, arr);
    }

    long query(int u, long kv) {
        for (auto& a : lift) {
            a.advance(u, kv, arr);
        }
        lift_last.advance(u, kv, arr);

        assert(u == n);
        return kv;
    }
} solver;

void init(int n,
          vector<int> arr_s,
          vector<int> arr_p,
          vector<int> arr_w,
          vector<int> arr_l) {
    vector<Dungeon> arr;
    for (int i = 0; i < n; i++) {
        arr.push_back({arr_s[i], arr_p[i], arr_w[i], arr_l[i]});
    }

    solver.build(arr);
    dbg(&solver.arr);

    // size_t c = 0;
    // for (auto& a : solver.lift) {
    //     for (auto& b : a.lift) {
    //         if (sz(b) != b.capacity()) {
    //             cout << sz(b) << " " << b.capacity() << endl;
    //         }
    //         c += b.capacity() * sizeof(DS1::Lift);
    //     }
    // }
    // cout << (c >> 20) << endl;
    // exit(0);
}

ll simulate(int u, int kv) {
    dbg(&solver.arr);
    return solver.query(u, kv);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 10 ms 8952 KB Output is correct
4 Correct 263 ms 215832 KB Output is correct
5 Correct 10 ms 8916 KB Output is correct
6 Correct 264 ms 215672 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4564 KB Output is correct
2 Correct 2289 ms 1723884 KB Output is correct
3 Correct 2122 ms 1723932 KB Output is correct
4 Correct 2588 ms 1725420 KB Output is correct
5 Correct 2165 ms 1725496 KB Output is correct
6 Correct 3938 ms 1723868 KB Output is correct
7 Correct 3269 ms 1722116 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4564 KB Output is correct
2 Correct 321 ms 215604 KB Output is correct
3 Correct 454 ms 215616 KB Output is correct
4 Correct 305 ms 215660 KB Output is correct
5 Correct 305 ms 215588 KB Output is correct
6 Correct 604 ms 215544 KB Output is correct
7 Correct 763 ms 215656 KB Output is correct
8 Correct 640 ms 215540 KB Output is correct
9 Correct 326 ms 215536 KB Output is correct
10 Correct 571 ms 215724 KB Output is correct
11 Correct 1042 ms 215612 KB Output is correct
12 Correct 5808 ms 215624 KB Output is correct
13 Correct 3335 ms 216008 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4564 KB Output is correct
2 Correct 321 ms 215604 KB Output is correct
3 Correct 454 ms 215616 KB Output is correct
4 Correct 305 ms 215660 KB Output is correct
5 Correct 305 ms 215588 KB Output is correct
6 Correct 604 ms 215544 KB Output is correct
7 Correct 763 ms 215656 KB Output is correct
8 Correct 640 ms 215540 KB Output is correct
9 Correct 326 ms 215536 KB Output is correct
10 Correct 571 ms 215724 KB Output is correct
11 Correct 1042 ms 215612 KB Output is correct
12 Correct 5808 ms 215624 KB Output is correct
13 Correct 3335 ms 216008 KB Output is correct
14 Correct 6 ms 4564 KB Output is correct
15 Correct 376 ms 215992 KB Output is correct
16 Correct 447 ms 216044 KB Output is correct
17 Correct 418 ms 215964 KB Output is correct
18 Correct 421 ms 215928 KB Output is correct
19 Correct 632 ms 215992 KB Output is correct
20 Correct 553 ms 215840 KB Output is correct
21 Correct 734 ms 215932 KB Output is correct
22 Correct 988 ms 215948 KB Output is correct
23 Correct 2251 ms 216072 KB Output is correct
24 Correct 2312 ms 215876 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4564 KB Output is correct
2 Correct 321 ms 215604 KB Output is correct
3 Correct 454 ms 215616 KB Output is correct
4 Correct 305 ms 215660 KB Output is correct
5 Correct 305 ms 215588 KB Output is correct
6 Correct 604 ms 215544 KB Output is correct
7 Correct 763 ms 215656 KB Output is correct
8 Correct 640 ms 215540 KB Output is correct
9 Correct 326 ms 215536 KB Output is correct
10 Correct 571 ms 215724 KB Output is correct
11 Correct 1042 ms 215612 KB Output is correct
12 Correct 5808 ms 215624 KB Output is correct
13 Correct 3335 ms 216008 KB Output is correct
14 Correct 6 ms 4564 KB Output is correct
15 Correct 376 ms 215992 KB Output is correct
16 Correct 447 ms 216044 KB Output is correct
17 Correct 418 ms 215964 KB Output is correct
18 Correct 421 ms 215928 KB Output is correct
19 Correct 632 ms 215992 KB Output is correct
20 Correct 553 ms 215840 KB Output is correct
21 Correct 734 ms 215932 KB Output is correct
22 Correct 988 ms 215948 KB Output is correct
23 Correct 2251 ms 216072 KB Output is correct
24 Correct 2312 ms 215876 KB Output is correct
25 Correct 286 ms 215328 KB Output is correct
26 Correct 364 ms 216048 KB Output is correct
27 Correct 344 ms 215868 KB Output is correct
28 Correct 323 ms 215864 KB Output is correct
29 Correct 445 ms 216020 KB Output is correct
30 Correct 605 ms 215968 KB Output is correct
31 Correct 777 ms 215792 KB Output is correct
32 Correct 1200 ms 215864 KB Output is correct
33 Correct 845 ms 215908 KB Output is correct
34 Correct 1625 ms 215724 KB Output is correct
35 Correct 1002 ms 215828 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4564 KB Output is correct
2 Correct 2289 ms 1723884 KB Output is correct
3 Correct 2122 ms 1723932 KB Output is correct
4 Correct 2588 ms 1725420 KB Output is correct
5 Correct 2165 ms 1725496 KB Output is correct
6 Correct 3938 ms 1723868 KB Output is correct
7 Correct 3269 ms 1722116 KB Output is correct
8 Correct 6 ms 4564 KB Output is correct
9 Correct 321 ms 215604 KB Output is correct
10 Correct 454 ms 215616 KB Output is correct
11 Correct 305 ms 215660 KB Output is correct
12 Correct 305 ms 215588 KB Output is correct
13 Correct 604 ms 215544 KB Output is correct
14 Correct 763 ms 215656 KB Output is correct
15 Correct 640 ms 215540 KB Output is correct
16 Correct 326 ms 215536 KB Output is correct
17 Correct 571 ms 215724 KB Output is correct
18 Correct 1042 ms 215612 KB Output is correct
19 Correct 5808 ms 215624 KB Output is correct
20 Correct 3335 ms 216008 KB Output is correct
21 Correct 6 ms 4564 KB Output is correct
22 Correct 376 ms 215992 KB Output is correct
23 Correct 447 ms 216044 KB Output is correct
24 Correct 418 ms 215964 KB Output is correct
25 Correct 421 ms 215928 KB Output is correct
26 Correct 632 ms 215992 KB Output is correct
27 Correct 553 ms 215840 KB Output is correct
28 Correct 734 ms 215932 KB Output is correct
29 Correct 988 ms 215948 KB Output is correct
30 Correct 2251 ms 216072 KB Output is correct
31 Correct 2312 ms 215876 KB Output is correct
32 Correct 286 ms 215328 KB Output is correct
33 Correct 364 ms 216048 KB Output is correct
34 Correct 344 ms 215868 KB Output is correct
35 Correct 323 ms 215864 KB Output is correct
36 Correct 445 ms 216020 KB Output is correct
37 Correct 605 ms 215968 KB Output is correct
38 Correct 777 ms 215792 KB Output is correct
39 Correct 1200 ms 215864 KB Output is correct
40 Correct 845 ms 215908 KB Output is correct
41 Correct 1625 ms 215724 KB Output is correct
42 Correct 1002 ms 215828 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 6 ms 4608 KB Output is correct
45 Correct 2602 ms 1728764 KB Output is correct
46 Correct 2205 ms 1723952 KB Output is correct
47 Correct 2248 ms 1724356 KB Output is correct
48 Correct 2619 ms 1726620 KB Output is correct
49 Correct 3139 ms 1728612 KB Output is correct
50 Correct 2990 ms 1726208 KB Output is correct
51 Correct 2272 ms 1726556 KB Output is correct
52 Correct 3252 ms 1724208 KB Output is correct
53 Correct 5102 ms 1725028 KB Output is correct
54 Correct 3309 ms 1726068 KB Output is correct
55 Correct 4589 ms 1725256 KB Output is correct
56 Correct 3882 ms 1725724 KB Output is correct
57 Correct 3921 ms 1725972 KB Output is correct
58 Correct 4178 ms 1725932 KB Output is correct
59 Correct 3918 ms 1726128 KB Output is correct
60 Correct 4971 ms 1725312 KB Output is correct
61 Correct 4354 ms 1725296 KB Output is correct