oj.uz

Submission #794657

# Submission time Handle Problem Language Result Execution time Memory
794657 2023-07-26T18:40:12 Z finn__ Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 1479520 KB 
#include <bits/stdc++.h>

#include "dungeons.h"

using namespace std;

constexpr size_t N = 400001, K = 26, 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];
                if (intermediate == n)
                    m[k][j][i] = UINT32_MAX;

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

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

    while (x != n)
    {
        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;
            }
        if (x != n)
        {
            if (strength >= s[x])
            {
                strength += s[x];
                x = w[x];
            }
            else
            {
                strength += p[x];
                x = l[x];
            }
        }
    }

    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:58:14: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     while (x != n)
      |            ~~^~~~
dungeons.cpp:69:15: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         if (x != n)
      |             ~~^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5460 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 6 ms 12736 KB Output is correct
4 Correct 110 ms 190064 KB Output is correct
5 Correct 7 ms 12756 KB Output is correct
6 Correct 107 ms 190004 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9044 KB Output is correct
2 Correct 1083 ms 1479460 KB Output is correct
3 Correct 863 ms 1479500 KB Output is correct
4 Correct 874 ms 1479392 KB Output is correct
5 Correct 908 ms 1479500 KB Output is correct
6 Correct 1012 ms 1479520 KB Output is correct
7 Correct 993 ms 1479432 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9044 KB Output is correct
2 Correct 171 ms 191180 KB Output is correct
3 Correct 4928 ms 191412 KB Output is correct
4 Correct 148 ms 191176 KB Output is correct
5 Correct 149 ms 191180 KB Output is correct
6 Correct 229 ms 191204 KB Output is correct
7 Correct 204 ms 191248 KB Output is correct
8 Correct 183 ms 191052 KB Output is correct
9 Correct 159 ms 191024 KB Output is correct
10 Correct 183 ms 191040 KB Output is correct
11 Correct 198 ms 191032 KB Output is correct
12 Correct 289 ms 191312 KB Output is correct
13 Correct 195 ms 191196 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9044 KB Output is correct
2 Correct 171 ms 191180 KB Output is correct
3 Correct 4928 ms 191412 KB Output is correct
4 Correct 148 ms 191176 KB Output is correct
5 Correct 149 ms 191180 KB Output is correct
6 Correct 229 ms 191204 KB Output is correct
7 Correct 204 ms 191248 KB Output is correct
8 Correct 183 ms 191052 KB Output is correct
9 Correct 159 ms 191024 KB Output is correct
10 Correct 183 ms 191040 KB Output is correct
11 Correct 198 ms 191032 KB Output is correct
12 Correct 289 ms 191312 KB Output is correct
13 Correct 195 ms 191196 KB Output is correct
14 Correct 5 ms 9172 KB Output is correct
15 Correct 151 ms 191204 KB Output is correct
16 Correct 169 ms 191156 KB Output is correct
17 Correct 153 ms 191236 KB Output is correct
18 Correct 148 ms 191148 KB Output is correct
19 Correct 230 ms 191180 KB Output is correct
20 Correct 199 ms 191176 KB Output is correct
21 Correct 190 ms 191156 KB Output is correct
22 Correct 200 ms 191052 KB Output is correct
23 Correct 254 ms 191072 KB Output is correct
24 Correct 315 ms 191176 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9044 KB Output is correct
2 Correct 171 ms 191180 KB Output is correct
3 Correct 4928 ms 191412 KB Output is correct
4 Correct 148 ms 191176 KB Output is correct
5 Correct 149 ms 191180 KB Output is correct
6 Correct 229 ms 191204 KB Output is correct
7 Correct 204 ms 191248 KB Output is correct
8 Correct 183 ms 191052 KB Output is correct
9 Correct 159 ms 191024 KB Output is correct
10 Correct 183 ms 191040 KB Output is correct
11 Correct 198 ms 191032 KB Output is correct
12 Correct 289 ms 191312 KB Output is correct
13 Correct 195 ms 191196 KB Output is correct
14 Correct 5 ms 9172 KB Output is correct
15 Correct 151 ms 191204 KB Output is correct
16 Correct 169 ms 191156 KB Output is correct
17 Correct 153 ms 191236 KB Output is correct
18 Correct 148 ms 191148 KB Output is correct
19 Correct 230 ms 191180 KB Output is correct
20 Correct 199 ms 191176 KB Output is correct
21 Correct 190 ms 191156 KB Output is correct
22 Correct 200 ms 191052 KB Output is correct
23 Correct 254 ms 191072 KB Output is correct
24 Correct 315 ms 191176 KB Output is correct
25 Correct 129 ms 190028 KB Output is correct
26 Correct 170 ms 191196 KB Output is correct
27 Correct 148 ms 191152 KB Output is correct
28 Correct 152 ms 191196 KB Output is correct
29 Correct 197 ms 191176 KB Output is correct
30 Correct 222 ms 191180 KB Output is correct
31 Correct 227 ms 191180 KB Output is correct
32 Correct 416 ms 191192 KB Output is correct
33 Correct 891 ms 191264 KB Output is correct
34 Correct 1797 ms 191248 KB Output is correct
35 Correct 793 ms 191304 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9044 KB Output is correct
2 Correct 1083 ms 1479460 KB Output is correct
3 Correct 863 ms 1479500 KB Output is correct
4 Correct 874 ms 1479392 KB Output is correct
5 Correct 908 ms 1479500 KB Output is correct
6 Correct 1012 ms 1479520 KB Output is correct
7 Correct 993 ms 1479432 KB Output is correct
8 Correct 5 ms 9044 KB Output is correct
9 Correct 171 ms 191180 KB Output is correct
10 Correct 4928 ms 191412 KB Output is correct
11 Correct 148 ms 191176 KB Output is correct
12 Correct 149 ms 191180 KB Output is correct
13 Correct 229 ms 191204 KB Output is correct
14 Correct 204 ms 191248 KB Output is correct
15 Correct 183 ms 191052 KB Output is correct
16 Correct 159 ms 191024 KB Output is correct
17 Correct 183 ms 191040 KB Output is correct
18 Correct 198 ms 191032 KB Output is correct
19 Correct 289 ms 191312 KB Output is correct
20 Correct 195 ms 191196 KB Output is correct
21 Correct 5 ms 9172 KB Output is correct
22 Correct 151 ms 191204 KB Output is correct
23 Correct 169 ms 191156 KB Output is correct
24 Correct 153 ms 191236 KB Output is correct
25 Correct 148 ms 191148 KB Output is correct
26 Correct 230 ms 191180 KB Output is correct
27 Correct 199 ms 191176 KB Output is correct
28 Correct 190 ms 191156 KB Output is correct
29 Correct 200 ms 191052 KB Output is correct
30 Correct 254 ms 191072 KB Output is correct
31 Correct 315 ms 191176 KB Output is correct
32 Correct 129 ms 190028 KB Output is correct
33 Correct 170 ms 191196 KB Output is correct
34 Correct 148 ms 191152 KB Output is correct
35 Correct 152 ms 191196 KB Output is correct
36 Correct 197 ms 191176 KB Output is correct
37 Correct 222 ms 191180 KB Output is correct
38 Correct 227 ms 191180 KB Output is correct
39 Correct 416 ms 191192 KB Output is correct
40 Correct 891 ms 191264 KB Output is correct
41 Correct 1797 ms 191248 KB Output is correct
42 Correct 793 ms 191304 KB Output is correct
43 Correct 2 ms 5460 KB Output is correct
44 Correct 5 ms 9172 KB Output is correct
45 Correct 1064 ms 1479444 KB Output is correct
46 Correct 882 ms 1479356 KB Output is correct
47 Correct 895 ms 1479320 KB Output is correct
48 Execution timed out 7174 ms 1478968 KB Time limit exceeded
49 Halted 0 ms 0 KB -