oj.uz

Submission #442805

# Submission time Handle Problem Language Result Execution time Memory
442805 2021-07-09T07:29:25 Z SorahISA Dungeons Game (IOI21_dungeons) C++17
100 / 100
 5857 ms 1127568 KB 
#include "dungeons.h"
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long
// #define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)

namespace {

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 4E5 + 5;
// const int maxn = 5E4 + 5;
const int lgmx = 24 + 1;
const int INF = 1E13;

int N;
vector<int> S, P, W, L;

vector<int> dep(maxn);

int sum[lgmx/4+1][lgmx][maxn];
int32_t anc[lgmx/4+1][lgmx][maxn], mnm[lgmx/4+1][lgmx][maxn];

} /// end of namespace

void init(int32_t _N, vector<int32_t> _S, vector<int32_t> _P, vector<int32_t> _W, vector<int32_t> _L) {
    N = _N;
    for (auto &x : _S) S.eb(x);
    for (auto &x : _P) P.eb(x);
    for (auto &x : _W) W.eb(x);
    for (auto &x : _L) L.eb(x);
    S.eb(0), P.eb(0), W.eb(N), L.eb(N);
    
    memset(anc, 0x00, sizeof(anc));
    memset(sum, 0x00, sizeof(sum));
    memset(mnm, 0x00, sizeof(mnm));
    
    for (int i = N-1; i >= 0; --i) dep[i] = dep[W[i]] + S[i];
    
    for (int lvl = 0; lvl <= lgmx/4; ++lvl) {
        
        /**
         * Assume strength is in [2^{4*lvl-4}, 2^{4*lvl}), every opponent with strength
         * greater or equal to 2^{4*lvl} is ignored and you lose immediately as we
         * only consider opponents with strength less than 2^{4*lvl} in this level.
        **/
        
        for (int i = 0; i <= N; ++i) {
            anc[lvl][0][i] = S[i] < (1<<(4*lvl)) ? W[i] : L[i];
            sum[lvl][0][i] = S[i] < (1<<(4*lvl)) ? S[i] : P[i];
            mnm[lvl][0][i] = S[i] < (1<<(4*lvl)) ? INF  : S[i];
        }
        
        for (int lay = 1; lay < lgmx; ++lay) {
            for (int i = 0; i <= N; ++i) {
                int32_t par = anc[lvl][lay-1][i];
                anc[lvl][lay][i] = anc[lvl][lay-1][par];
                sum[lvl][lay][i] = sum[lvl][lay-1][i] + sum[lvl][lay-1][par];
                int32_t tmp = mnm[lvl][lay-1][par];
                if (tmp != INF) tmp -= sum[lvl][lay-1][i];
                mnm[lvl][lay][i] = min(mnm[lvl][lay-1][i], max(0, tmp));
            }
        }
        
    }
}

int simulate(int32_t now, int32_t _Z) {
    int Z = _Z;
    for (int lvl = 0; lvl <= lgmx/4; ++lvl) {
        // int lvl = __lg(Z) / 4;
        for (int _ = 0; _ < 16; ++_) {
            for (int lay = lgmx-1; lay >= 0; --lay) {
                if (Z < mnm[lvl][lay][now]) {
                    Z += sum[lvl][lay][now];
                    now = anc[lvl][lay][now]; 
                }
            }
            // cerr << "lvl = " << lvl << ", Z = " << Z << ", now = " << now << "\n";
            if (Z >= S[now]) Z += S[now], now = W[now];
            else             Z += P[now], now = L[now];
            // cerr << "lvl = " << lvl << ", Z = " << Z << ", now = " << now << "\n";
        }
    }
    return Z + dep[now];
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 1099216 KB Output is correct
2 Correct 500 ms 1099280 KB Output is correct
3 Correct 504 ms 1099400 KB Output is correct
4 Correct 574 ms 1102844 KB Output is correct
5 Correct 500 ms 1099352 KB Output is correct
6 Correct 573 ms 1102820 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 1099360 KB Output is correct
2 Correct 2103 ms 1125752 KB Output is correct
3 Correct 2065 ms 1125484 KB Output is correct
4 Correct 2162 ms 1125344 KB Output is correct
5 Correct 2349 ms 1125396 KB Output is correct
6 Correct 2059 ms 1125392 KB Output is correct
7 Correct 2971 ms 1125404 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 1099324 KB Output is correct
2 Correct 1583 ms 1103560 KB Output is correct
3 Correct 1160 ms 1103420 KB Output is correct
4 Correct 1475 ms 1103432 KB Output is correct
5 Correct 1476 ms 1103428 KB Output is correct
6 Correct 1649 ms 1103548 KB Output is correct
7 Correct 1643 ms 1103456 KB Output is correct
8 Correct 1487 ms 1103348 KB Output is correct
9 Correct 1577 ms 1103444 KB Output is correct
10 Correct 1474 ms 1103420 KB Output is correct
11 Correct 1552 ms 1103448 KB Output is correct
12 Correct 1060 ms 1103428 KB Output is correct
13 Correct 1663 ms 1103432 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 1099324 KB Output is correct
2 Correct 1583 ms 1103560 KB Output is correct
3 Correct 1160 ms 1103420 KB Output is correct
4 Correct 1475 ms 1103432 KB Output is correct
5 Correct 1476 ms 1103428 KB Output is correct
6 Correct 1649 ms 1103548 KB Output is correct
7 Correct 1643 ms 1103456 KB Output is correct
8 Correct 1487 ms 1103348 KB Output is correct
9 Correct 1577 ms 1103444 KB Output is correct
10 Correct 1474 ms 1103420 KB Output is correct
11 Correct 1552 ms 1103448 KB Output is correct
12 Correct 1060 ms 1103428 KB Output is correct
13 Correct 1663 ms 1103432 KB Output is correct
14 Correct 505 ms 1099404 KB Output is correct
15 Correct 1510 ms 1103456 KB Output is correct
16 Correct 1615 ms 1103496 KB Output is correct
17 Correct 1467 ms 1103460 KB Output is correct
18 Correct 1467 ms 1103432 KB Output is correct
19 Correct 1669 ms 1103472 KB Output is correct
20 Correct 1470 ms 1103472 KB Output is correct
21 Correct 1431 ms 1103332 KB Output is correct
22 Correct 1541 ms 1103440 KB Output is correct
23 Correct 1511 ms 1103348 KB Output is correct
24 Correct 1709 ms 1103420 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 1099324 KB Output is correct
2 Correct 1583 ms 1103560 KB Output is correct
3 Correct 1160 ms 1103420 KB Output is correct
4 Correct 1475 ms 1103432 KB Output is correct
5 Correct 1476 ms 1103428 KB Output is correct
6 Correct 1649 ms 1103548 KB Output is correct
7 Correct 1643 ms 1103456 KB Output is correct
8 Correct 1487 ms 1103348 KB Output is correct
9 Correct 1577 ms 1103444 KB Output is correct
10 Correct 1474 ms 1103420 KB Output is correct
11 Correct 1552 ms 1103448 KB Output is correct
12 Correct 1060 ms 1103428 KB Output is correct
13 Correct 1663 ms 1103432 KB Output is correct
14 Correct 505 ms 1099404 KB Output is correct
15 Correct 1510 ms 1103456 KB Output is correct
16 Correct 1615 ms 1103496 KB Output is correct
17 Correct 1467 ms 1103460 KB Output is correct
18 Correct 1467 ms 1103432 KB Output is correct
19 Correct 1669 ms 1103472 KB Output is correct
20 Correct 1470 ms 1103472 KB Output is correct
21 Correct 1431 ms 1103332 KB Output is correct
22 Correct 1541 ms 1103440 KB Output is correct
23 Correct 1511 ms 1103348 KB Output is correct
24 Correct 1709 ms 1103420 KB Output is correct
25 Correct 607 ms 1102784 KB Output is correct
26 Correct 1590 ms 1103664 KB Output is correct
27 Correct 1531 ms 1103572 KB Output is correct
28 Correct 1580 ms 1103560 KB Output is correct
29 Correct 1640 ms 1103432 KB Output is correct
30 Correct 1324 ms 1103472 KB Output is correct
31 Correct 1313 ms 1103452 KB Output is correct
32 Correct 1633 ms 1103480 KB Output is correct
33 Correct 2079 ms 1103360 KB Output is correct
34 Correct 2896 ms 1103584 KB Output is correct
35 Correct 2739 ms 1103492 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 1099360 KB Output is correct
2 Correct 2103 ms 1125752 KB Output is correct
3 Correct 2065 ms 1125484 KB Output is correct
4 Correct 2162 ms 1125344 KB Output is correct
5 Correct 2349 ms 1125396 KB Output is correct
6 Correct 2059 ms 1125392 KB Output is correct
7 Correct 2971 ms 1125404 KB Output is correct
8 Correct 511 ms 1099324 KB Output is correct
9 Correct 1583 ms 1103560 KB Output is correct
10 Correct 1160 ms 1103420 KB Output is correct
11 Correct 1475 ms 1103432 KB Output is correct
12 Correct 1476 ms 1103428 KB Output is correct
13 Correct 1649 ms 1103548 KB Output is correct
14 Correct 1643 ms 1103456 KB Output is correct
15 Correct 1487 ms 1103348 KB Output is correct
16 Correct 1577 ms 1103444 KB Output is correct
17 Correct 1474 ms 1103420 KB Output is correct
18 Correct 1552 ms 1103448 KB Output is correct
19 Correct 1060 ms 1103428 KB Output is correct
20 Correct 1663 ms 1103432 KB Output is correct
21 Correct 505 ms 1099404 KB Output is correct
22 Correct 1510 ms 1103456 KB Output is correct
23 Correct 1615 ms 1103496 KB Output is correct
24 Correct 1467 ms 1103460 KB Output is correct
25 Correct 1467 ms 1103432 KB Output is correct
26 Correct 1669 ms 1103472 KB Output is correct
27 Correct 1470 ms 1103472 KB Output is correct
28 Correct 1431 ms 1103332 KB Output is correct
29 Correct 1541 ms 1103440 KB Output is correct
30 Correct 1511 ms 1103348 KB Output is correct
31 Correct 1709 ms 1103420 KB Output is correct
32 Correct 607 ms 1102784 KB Output is correct
33 Correct 1590 ms 1103664 KB Output is correct
34 Correct 1531 ms 1103572 KB Output is correct
35 Correct 1580 ms 1103560 KB Output is correct
36 Correct 1640 ms 1103432 KB Output is correct
37 Correct 1324 ms 1103472 KB Output is correct
38 Correct 1313 ms 1103452 KB Output is correct
39 Correct 1633 ms 1103480 KB Output is correct
40 Correct 2079 ms 1103360 KB Output is correct
41 Correct 2896 ms 1103584 KB Output is correct
42 Correct 2739 ms 1103492 KB Output is correct
43 Correct 487 ms 1099332 KB Output is correct
44 Correct 506 ms 1099468 KB Output is correct
45 Correct 2677 ms 1127568 KB Output is correct
46 Correct 2409 ms 1126872 KB Output is correct
47 Correct 2472 ms 1126944 KB Output is correct
48 Correct 1866 ms 1127016 KB Output is correct
49 Correct 2796 ms 1127148 KB Output is correct
50 Correct 2123 ms 1126884 KB Output is correct
51 Correct 1387 ms 1126956 KB Output is correct
52 Correct 2049 ms 1126972 KB Output is correct
53 Correct 3713 ms 1126956 KB Output is correct
54 Correct 3374 ms 1127148 KB Output is correct
55 Correct 4369 ms 1127288 KB Output is correct
56 Correct 5556 ms 1127000 KB Output is correct
57 Correct 5670 ms 1127308 KB Output is correct
58 Correct 5857 ms 1127212 KB Output is correct
59 Correct 5230 ms 1127176 KB Output is correct
60 Correct 4886 ms 1127032 KB Output is correct
61 Correct 4939 ms 1127468 KB Output is correct