oj.uz

Submission #794682

# Submission time Handle Problem Language Result Execution time Memory
794682 2023-07-26T19:01:28 Z finn__ Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 1423128 KB 
#include <bits/stdc++.h>

#include "dungeons.h"

using namespace std;

constexpr size_t N = 400001, K = 25, L = 9;

size_t n;
uint32_t f[L][K][N], m[L][K][N];
uint64_t u[L][K][N];
vector<int> s, p, w, l;

void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_)
{
    n = n_;
    s = move(s_);
    p = move(p_);
    w = move(w_);
    l = move(l_);

    for (size_t k = 0; k < L; ++k)
    {
        for (size_t i = 0; i < n; ++i)
        {
            if (s[i] < 1ULL << (k * 3))
                f[k][0][i] = w[i], u[k][0][i] = s[i], m[k][0][i] = UINT32_MAX;
            else
                f[k][0][i] = l[i], u[k][0][i] = p[i], m[k][0][i] = s[i];
        }
        f[k][0][n] = n;
        u[k][0][n] = 0;
        m[k][0][n] = UINT32_MAX;
        for (size_t j = 1; j < K; ++j)
            for (size_t i = 0; i < n; ++i)
            {
                size_t const intermediate = f[k][j - 1][i];
                f[k][j][i] = f[k][j - 1][intermediate];
                u[k][j][i] = u[k][j - 1][i] + u[k][j - 1][intermediate];

                m[k][j][i] = m[k][j - 1][i];
                if (m[k][j - 1][intermediate] != UINT32_MAX)
                {
                    uint32_t v = m[k][j - 1][intermediate] - min<uint64_t>(m[k][j - 1][intermediate],
                                                                           u[k][j - 1][i]);
                    m[k][j][i] = min(m[k][j][i], v);
                }
            }
    }
}

long long simulate(int x, int z)
{
    long long strength = z;

    while (x != n)
    {
        if (strength >= s[x])
        {
            strength += s[x];
            x = w[x];
        }
        else
        {
            strength += p[x];
            x = l[x];
        }
        size_t const k = min<size_t>(L - 1, __lg(strength) / 3);

        for (size_t j = K - 1; j < K; --j)
            if (m[k][j][x] > strength)
            {
                strength += u[k][j][x];
                x = f[k][j][x];
                break;
            }
    }

    return strength;
}

Compilation message

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:26:22: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'long long unsigned int' [-Wsign-compare]
   26 |             if (s[i] < 1ULL << (k * 3))
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:56:14: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     while (x != n)
      |            ~~^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 6 ms 12244 KB Output is correct
4 Correct 117 ms 182732 KB Output is correct
5 Correct 9 ms 12244 KB Output is correct
6 Correct 113 ms 182660 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8788 KB Output is correct
2 Correct 909 ms 1423004 KB Output is correct
3 Correct 836 ms 1422956 KB Output is correct
4 Correct 858 ms 1423004 KB Output is correct
5 Correct 867 ms 1423024 KB Output is correct
6 Correct 925 ms 1423052 KB Output is correct
7 Correct 900 ms 1423052 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8788 KB Output is correct
2 Correct 147 ms 184016 KB Output is correct
3 Correct 5055 ms 184072 KB Output is correct
4 Correct 132 ms 183944 KB Output is correct
5 Correct 132 ms 183896 KB Output is correct
6 Correct 183 ms 184012 KB Output is correct
7 Correct 176 ms 183904 KB Output is correct
8 Correct 160 ms 183884 KB Output is correct
9 Correct 138 ms 183808 KB Output is correct
10 Correct 161 ms 183884 KB Output is correct
11 Correct 184 ms 183764 KB Output is correct
12 Correct 235 ms 184108 KB Output is correct
13 Correct 172 ms 183900 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8788 KB Output is correct
2 Correct 147 ms 184016 KB Output is correct
3 Correct 5055 ms 184072 KB Output is correct
4 Correct 132 ms 183944 KB Output is correct
5 Correct 132 ms 183896 KB Output is correct
6 Correct 183 ms 184012 KB Output is correct
7 Correct 176 ms 183904 KB Output is correct
8 Correct 160 ms 183884 KB Output is correct
9 Correct 138 ms 183808 KB Output is correct
10 Correct 161 ms 183884 KB Output is correct
11 Correct 184 ms 183764 KB Output is correct
12 Correct 235 ms 184108 KB Output is correct
13 Correct 172 ms 183900 KB Output is correct
14 Correct 4 ms 8788 KB Output is correct
15 Correct 136 ms 183972 KB Output is correct
16 Correct 141 ms 184012 KB Output is correct
17 Correct 134 ms 183884 KB Output is correct
18 Correct 134 ms 183988 KB Output is correct
19 Correct 186 ms 183956 KB Output is correct
20 Correct 162 ms 183916 KB Output is correct
21 Correct 169 ms 183944 KB Output is correct
22 Correct 168 ms 183828 KB Output is correct
23 Correct 222 ms 183884 KB Output is correct
24 Correct 263 ms 183944 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8788 KB Output is correct
2 Correct 147 ms 184016 KB Output is correct
3 Correct 5055 ms 184072 KB Output is correct
4 Correct 132 ms 183944 KB Output is correct
5 Correct 132 ms 183896 KB Output is correct
6 Correct 183 ms 184012 KB Output is correct
7 Correct 176 ms 183904 KB Output is correct
8 Correct 160 ms 183884 KB Output is correct
9 Correct 138 ms 183808 KB Output is correct
10 Correct 161 ms 183884 KB Output is correct
11 Correct 184 ms 183764 KB Output is correct
12 Correct 235 ms 184108 KB Output is correct
13 Correct 172 ms 183900 KB Output is correct
14 Correct 4 ms 8788 KB Output is correct
15 Correct 136 ms 183972 KB Output is correct
16 Correct 141 ms 184012 KB Output is correct
17 Correct 134 ms 183884 KB Output is correct
18 Correct 134 ms 183988 KB Output is correct
19 Correct 186 ms 183956 KB Output is correct
20 Correct 162 ms 183916 KB Output is correct
21 Correct 169 ms 183944 KB Output is correct
22 Correct 168 ms 183828 KB Output is correct
23 Correct 222 ms 183884 KB Output is correct
24 Correct 263 ms 183944 KB Output is correct
25 Correct 112 ms 182688 KB Output is correct
26 Correct 145 ms 183948 KB Output is correct
27 Correct 138 ms 183912 KB Output is correct
28 Correct 137 ms 183900 KB Output is correct
29 Correct 149 ms 183948 KB Output is correct
30 Correct 185 ms 183932 KB Output is correct
31 Correct 198 ms 183904 KB Output is correct
32 Correct 339 ms 183928 KB Output is correct
33 Correct 812 ms 184024 KB Output is correct
34 Correct 1492 ms 184024 KB Output is correct
35 Correct 651 ms 184068 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8788 KB Output is correct
2 Correct 909 ms 1423004 KB Output is correct
3 Correct 836 ms 1422956 KB Output is correct
4 Correct 858 ms 1423004 KB Output is correct
5 Correct 867 ms 1423024 KB Output is correct
6 Correct 925 ms 1423052 KB Output is correct
7 Correct 900 ms 1423052 KB Output is correct
8 Correct 4 ms 8788 KB Output is correct
9 Correct 147 ms 184016 KB Output is correct
10 Correct 5055 ms 184072 KB Output is correct
11 Correct 132 ms 183944 KB Output is correct
12 Correct 132 ms 183896 KB Output is correct
13 Correct 183 ms 184012 KB Output is correct
14 Correct 176 ms 183904 KB Output is correct
15 Correct 160 ms 183884 KB Output is correct
16 Correct 138 ms 183808 KB Output is correct
17 Correct 161 ms 183884 KB Output is correct
18 Correct 184 ms 183764 KB Output is correct
19 Correct 235 ms 184108 KB Output is correct
20 Correct 172 ms 183900 KB Output is correct
21 Correct 4 ms 8788 KB Output is correct
22 Correct 136 ms 183972 KB Output is correct
23 Correct 141 ms 184012 KB Output is correct
24 Correct 134 ms 183884 KB Output is correct
25 Correct 134 ms 183988 KB Output is correct
26 Correct 186 ms 183956 KB Output is correct
27 Correct 162 ms 183916 KB Output is correct
28 Correct 169 ms 183944 KB Output is correct
29 Correct 168 ms 183828 KB Output is correct
30 Correct 222 ms 183884 KB Output is correct
31 Correct 263 ms 183944 KB Output is correct
32 Correct 112 ms 182688 KB Output is correct
33 Correct 145 ms 183948 KB Output is correct
34 Correct 138 ms 183912 KB Output is correct
35 Correct 137 ms 183900 KB Output is correct
36 Correct 149 ms 183948 KB Output is correct
37 Correct 185 ms 183932 KB Output is correct
38 Correct 198 ms 183904 KB Output is correct
39 Correct 339 ms 183928 KB Output is correct
40 Correct 812 ms 184024 KB Output is correct
41 Correct 1492 ms 184024 KB Output is correct
42 Correct 651 ms 184068 KB Output is correct
43 Correct 2 ms 5204 KB Output is correct
44 Correct 5 ms 8788 KB Output is correct
45 Correct 1014 ms 1423000 KB Output is correct
46 Correct 834 ms 1423128 KB Output is correct
47 Correct 843 ms 1422988 KB Output is correct
48 Execution timed out 7112 ms 1422616 KB Time limit exceeded
49 Halted 0 ms 0 KB -