oj.uz

Submission #815307

# Submission time Handle Problem Language Result Execution time Memory
815307 2023-08-08T14:06:32 Z eltu0815 Dungeons Game (IOI21_dungeons) C++17
100 / 100
 4918 ms 1591392 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int N;
const int MX = 8;
int pos[MX][400001][25];
ll mn[MX][400001][25], sum[MX][400001][25];
ll dp[400001];
 
 vector<int> s, p, w, l;
void init(int n, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
    N = n; s = S; p = P, w = W, l = L;
    for(int j = 0; j < MX; ++j) {
        for(int i = 0; i < N; ++i) {
            pos[j][i][0] = (1 << 3 * j) <= S[i] ? L[i] : W[i];
            sum[j][i][0] = (1 << 3 * j) <= S[i] ? P[i] : S[i];
            mn[j][i][0] = (1 << 3 * j) <= S[i] ? S[i] : (ll)(1e16);
        }
        pos[j][N][0] = N, sum[j][N][0] = 0;
    }
    for(int k = 0; k < MX; ++k) for(int j = 1; j < 25; ++j) {
        for(int i = 0; i <= N; ++i) {
            pos[k][i][j] = pos[k][pos[k][i][j - 1]][j - 1];
            sum[k][i][j] = sum[k][pos[k][i][j - 1]][j - 1] + sum[k][i][j - 1];
            mn[k][i][j] = min(mn[k][i][j - 1], mn[k][pos[k][i][j - 1]][j - 1] - sum[k][i][j - 1]);
        }
    }
    
    for(int i = n - 1; i >= 0; --i) dp[i] = dp[W[i]] + S[i];
	return;
}
 
long long simulate(int x, int z) {
    ll ans = z;
    for(int k = 0; k < MX; ++k) {
        while(ans < (1ll << 3 * k + 3)) {
            for(int j = 24; j >= 0; --j) {
                if(pos[k][x][j] != N && sum[k][x][j] + ans < (1 << 3 * k + 3) && mn[k][x][j] > ans) {
                    ans += sum[k][x][j], x = pos[k][x][j];
                }
            }
            if(s[x] <= ans) ans += s[x], x = w[x];
            else if(ans < (1 << 3 * k + 3)) ans += p[x], x = l[x];
            if(x == N) return ans;
        }
    }
	return ans + dp[x];
}

Compilation message

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:39:35: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   39 |         while(ans < (1ll << 3 * k + 3)) {
      |                             ~~~~~~^~~
dungeons.cpp:41:74: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   41 |                 if(pos[k][x][j] != N && sum[k][x][j] + ans < (1 << 3 * k + 3) && mn[k][x][j] > ans) {
      |                                                                    ~~~~~~^~~
dungeons.cpp:46:39: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   46 |             else if(ans < (1 << 3 * k + 3)) ans += p[x], x = l[x];
      |                                 ~~~~~~^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 444 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 5 ms 8404 KB Output is correct
4 Correct 335 ms 199592 KB Output is correct
5 Correct 7 ms 8396 KB Output is correct
6 Correct 215 ms 199656 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4436 KB Output is correct
2 Correct 3085 ms 1590440 KB Output is correct
3 Correct 3000 ms 1591340 KB Output is correct
4 Correct 2544 ms 1591392 KB Output is correct
5 Correct 2438 ms 1591208 KB Output is correct
6 Correct 3063 ms 1591088 KB Output is correct
7 Correct 2754 ms 1591080 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4512 KB Output is correct
2 Correct 333 ms 201364 KB Output is correct
3 Correct 238 ms 201532 KB Output is correct
4 Correct 308 ms 200900 KB Output is correct
5 Correct 355 ms 200724 KB Output is correct
6 Correct 383 ms 200984 KB Output is correct
7 Correct 340 ms 200900 KB Output is correct
8 Correct 367 ms 200728 KB Output is correct
9 Correct 258 ms 200720 KB Output is correct
10 Correct 443 ms 200600 KB Output is correct
11 Correct 632 ms 200908 KB Output is correct
12 Correct 1215 ms 201040 KB Output is correct
13 Correct 1035 ms 200984 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4512 KB Output is correct
2 Correct 333 ms 201364 KB Output is correct
3 Correct 238 ms 201532 KB Output is correct
4 Correct 308 ms 200900 KB Output is correct
5 Correct 355 ms 200724 KB Output is correct
6 Correct 383 ms 200984 KB Output is correct
7 Correct 340 ms 200900 KB Output is correct
8 Correct 367 ms 200728 KB Output is correct
9 Correct 258 ms 200720 KB Output is correct
10 Correct 443 ms 200600 KB Output is correct
11 Correct 632 ms 200908 KB Output is correct
12 Correct 1215 ms 201040 KB Output is correct
13 Correct 1035 ms 200984 KB Output is correct
14 Correct 4 ms 4436 KB Output is correct
15 Correct 303 ms 201116 KB Output is correct
16 Correct 360 ms 201352 KB Output is correct
17 Correct 332 ms 200852 KB Output is correct
18 Correct 314 ms 201052 KB Output is correct
19 Correct 370 ms 200988 KB Output is correct
20 Correct 393 ms 200732 KB Output is correct
21 Correct 386 ms 200756 KB Output is correct
22 Correct 428 ms 200736 KB Output is correct
23 Correct 642 ms 200992 KB Output is correct
24 Correct 802 ms 200980 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4512 KB Output is correct
2 Correct 333 ms 201364 KB Output is correct
3 Correct 238 ms 201532 KB Output is correct
4 Correct 308 ms 200900 KB Output is correct
5 Correct 355 ms 200724 KB Output is correct
6 Correct 383 ms 200984 KB Output is correct
7 Correct 340 ms 200900 KB Output is correct
8 Correct 367 ms 200728 KB Output is correct
9 Correct 258 ms 200720 KB Output is correct
10 Correct 443 ms 200600 KB Output is correct
11 Correct 632 ms 200908 KB Output is correct
12 Correct 1215 ms 201040 KB Output is correct
13 Correct 1035 ms 200984 KB Output is correct
14 Correct 4 ms 4436 KB Output is correct
15 Correct 303 ms 201116 KB Output is correct
16 Correct 360 ms 201352 KB Output is correct
17 Correct 332 ms 200852 KB Output is correct
18 Correct 314 ms 201052 KB Output is correct
19 Correct 370 ms 200988 KB Output is correct
20 Correct 393 ms 200732 KB Output is correct
21 Correct 386 ms 200756 KB Output is correct
22 Correct 428 ms 200736 KB Output is correct
23 Correct 642 ms 200992 KB Output is correct
24 Correct 802 ms 200980 KB Output is correct
25 Correct 282 ms 200304 KB Output is correct
26 Correct 303 ms 201336 KB Output is correct
27 Correct 282 ms 200764 KB Output is correct
28 Correct 274 ms 200788 KB Output is correct
29 Correct 359 ms 201240 KB Output is correct
30 Correct 421 ms 200984 KB Output is correct
31 Correct 492 ms 200724 KB Output is correct
32 Correct 668 ms 200852 KB Output is correct
33 Correct 624 ms 200896 KB Output is correct
34 Correct 1041 ms 200768 KB Output is correct
35 Correct 569 ms 200780 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4436 KB Output is correct
2 Correct 3085 ms 1590440 KB Output is correct
3 Correct 3000 ms 1591340 KB Output is correct
4 Correct 2544 ms 1591392 KB Output is correct
5 Correct 2438 ms 1591208 KB Output is correct
6 Correct 3063 ms 1591088 KB Output is correct
7 Correct 2754 ms 1591080 KB Output is correct
8 Correct 5 ms 4512 KB Output is correct
9 Correct 333 ms 201364 KB Output is correct
10 Correct 238 ms 201532 KB Output is correct
11 Correct 308 ms 200900 KB Output is correct
12 Correct 355 ms 200724 KB Output is correct
13 Correct 383 ms 200984 KB Output is correct
14 Correct 340 ms 200900 KB Output is correct
15 Correct 367 ms 200728 KB Output is correct
16 Correct 258 ms 200720 KB Output is correct
17 Correct 443 ms 200600 KB Output is correct
18 Correct 632 ms 200908 KB Output is correct
19 Correct 1215 ms 201040 KB Output is correct
20 Correct 1035 ms 200984 KB Output is correct
21 Correct 4 ms 4436 KB Output is correct
22 Correct 303 ms 201116 KB Output is correct
23 Correct 360 ms 201352 KB Output is correct
24 Correct 332 ms 200852 KB Output is correct
25 Correct 314 ms 201052 KB Output is correct
26 Correct 370 ms 200988 KB Output is correct
27 Correct 393 ms 200732 KB Output is correct
28 Correct 386 ms 200756 KB Output is correct
29 Correct 428 ms 200736 KB Output is correct
30 Correct 642 ms 200992 KB Output is correct
31 Correct 802 ms 200980 KB Output is correct
32 Correct 282 ms 200304 KB Output is correct
33 Correct 303 ms 201336 KB Output is correct
34 Correct 282 ms 200764 KB Output is correct
35 Correct 274 ms 200788 KB Output is correct
36 Correct 359 ms 201240 KB Output is correct
37 Correct 421 ms 200984 KB Output is correct
38 Correct 492 ms 200724 KB Output is correct
39 Correct 668 ms 200852 KB Output is correct
40 Correct 624 ms 200896 KB Output is correct
41 Correct 1041 ms 200768 KB Output is correct
42 Correct 569 ms 200780 KB Output is correct
43 Correct 1 ms 468 KB Output is correct
44 Correct 3 ms 4428 KB Output is correct
45 Correct 2901 ms 1590448 KB Output is correct
46 Correct 2378 ms 1590316 KB Output is correct
47 Correct 2355 ms 1590324 KB Output is correct
48 Correct 2188 ms 1590188 KB Output is correct
49 Correct 3413 ms 1590856 KB Output is correct
50 Correct 2916 ms 1591080 KB Output is correct
51 Correct 2355 ms 1590824 KB Output is correct
52 Correct 2814 ms 1590820 KB Output is correct
53 Correct 4898 ms 1589816 KB Output is correct
54 Correct 3591 ms 1590096 KB Output is correct
55 Correct 4618 ms 1589760 KB Output is correct
56 Correct 3764 ms 1589216 KB Output is correct
57 Correct 4504 ms 1588692 KB Output is correct
58 Correct 3792 ms 1588524 KB Output is correct
59 Correct 3811 ms 1588484 KB Output is correct
60 Correct 4721 ms 1588520 KB Output is correct
61 Correct 4918 ms 1588524 KB Output is correct