oj.uz

Submission #442523

# Submission time Handle Problem Language Result Execution time Memory
442523 2021-07-08T05:52:03 Z JovanB Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 1429008 KB 
#include "dungeons.h"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 400000;
const int LOG2 = 24;
const int LOG8 = 8;

const int INF = 1000000000;

int dp[LOG8+1][MAXN+5][LOG2+1];
ll dod[LOG8+1][MAXN+5][LOG2+1];
int gde[LOG8+1][MAXN+5][LOG2+1];

int s[MAXN+5];
int pl[MAXN+5];
int win[MAXN+5];
int lose[MAXN+5];
int step8[MAXN+5];

int N;

void init(int n, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L){
    N = n;
    for(int i=0; i<n; i++){
        s[i] = S[i];
        pl[i] = P[i];
        win[i] = W[i];
        lose[i] = L[i];
    }
    s[n] = 0;
    pl[n] = 0;
    win[n] = n;
    lose[n] = n;
    step8[0] = 1;
    for(int i=1; i<=LOG8; i++) step8[i] = 8*step8[i-1];
    for(int k=0; k<=LOG8; k++){
        for(int i=0; i<=n; i++){
            if(step8[k] >= s[i]){
                dp[k][i][0] = INF;
                dod[k][i][0] = s[i];
                gde[k][i][0] = win[i];
            }
            else{
                dp[k][i][0] = s[i] - 1;
                dod[k][i][0] = pl[i];
                gde[k][i][0] = lose[i];
            }
        }
        for(int j=1; j<=LOG2; j++){
            for(int i=0; i<=n; i++){
                int h = gde[k][i][j-1];
                int mndp = dp[k][i][j-1];
                ll udod = dod[k][i][j-1];
                for(int times=1; times<2; times++){
                    mndp = min(mndp, dp[k][h][j-1] == INF ? INF : dp[k][h][j-1] - (udod > INF ? INF : int(udod)));
                    udod += dod[k][h][j-1];
                    h = gde[k][h][j-1];
                }
                gde[k][i][j] = h;
                dod[k][i][j] = udod;
                dp[k][i][j] = max(mndp, -5);
            }
        }
    }
	return;
}

ll simuliraj(int x, ll z){
    if(x == N) return z;
    int k = 0;
    for(int j=0; j<=LOG8; j++){
        if(step8[j] <= z) k = j;
    }
    if(k == LOG8) return z + dod[k][x][20];
    for(int j=LOG2; j>=0; j--){
        if(dp[k][x][j] >= z){
            z += dod[k][x][j];
            x = gde[k][x][j];
        }
    }
    if(x == N) return z;
    if(z >= s[x]) return simuliraj(win[x], z + s[x]);
    return simuliraj(lose[x], z + pl[x]);
}

long long simulate(int x, int z) {
    return simuliraj(x, z);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 9 ms 7628 KB Output is correct
4 Correct 551 ms 179024 KB Output is correct
5 Correct 9 ms 7628 KB Output is correct
6 Correct 546 ms 179008 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4044 KB Output is correct
2 Correct 4902 ms 1428768 KB Output is correct
3 Correct 5877 ms 1428884 KB Output is correct
4 Correct 5524 ms 1428892 KB Output is correct
5 Correct 4461 ms 1428968 KB Output is correct
6 Correct 4490 ms 1428848 KB Output is correct
7 Correct 4535 ms 1428848 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4044 KB Output is correct
2 Correct 561 ms 179760 KB Output is correct
3 Correct 483 ms 179908 KB Output is correct
4 Correct 541 ms 179908 KB Output is correct
5 Correct 493 ms 179792 KB Output is correct
6 Correct 577 ms 179780 KB Output is correct
7 Correct 560 ms 179884 KB Output is correct
8 Correct 551 ms 179924 KB Output is correct
9 Correct 485 ms 179780 KB Output is correct
10 Correct 545 ms 179808 KB Output is correct
11 Correct 757 ms 179800 KB Output is correct
12 Correct 1016 ms 179760 KB Output is correct
13 Correct 676 ms 179792 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4044 KB Output is correct
2 Correct 561 ms 179760 KB Output is correct
3 Correct 483 ms 179908 KB Output is correct
4 Correct 541 ms 179908 KB Output is correct
5 Correct 493 ms 179792 KB Output is correct
6 Correct 577 ms 179780 KB Output is correct
7 Correct 560 ms 179884 KB Output is correct
8 Correct 551 ms 179924 KB Output is correct
9 Correct 485 ms 179780 KB Output is correct
10 Correct 545 ms 179808 KB Output is correct
11 Correct 757 ms 179800 KB Output is correct
12 Correct 1016 ms 179760 KB Output is correct
13 Correct 676 ms 179792 KB Output is correct
14 Correct 6 ms 4044 KB Output is correct
15 Correct 521 ms 179780 KB Output is correct
16 Correct 561 ms 179728 KB Output is correct
17 Correct 540 ms 179872 KB Output is correct
18 Correct 561 ms 179780 KB Output is correct
19 Correct 565 ms 179792 KB Output is correct
20 Correct 536 ms 179780 KB Output is correct
21 Correct 553 ms 179876 KB Output is correct
22 Correct 619 ms 179908 KB Output is correct
23 Correct 834 ms 179908 KB Output is correct
24 Correct 996 ms 179924 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4044 KB Output is correct
2 Correct 561 ms 179760 KB Output is correct
3 Correct 483 ms 179908 KB Output is correct
4 Correct 541 ms 179908 KB Output is correct
5 Correct 493 ms 179792 KB Output is correct
6 Correct 577 ms 179780 KB Output is correct
7 Correct 560 ms 179884 KB Output is correct
8 Correct 551 ms 179924 KB Output is correct
9 Correct 485 ms 179780 KB Output is correct
10 Correct 545 ms 179808 KB Output is correct
11 Correct 757 ms 179800 KB Output is correct
12 Correct 1016 ms 179760 KB Output is correct
13 Correct 676 ms 179792 KB Output is correct
14 Correct 6 ms 4044 KB Output is correct
15 Correct 521 ms 179780 KB Output is correct
16 Correct 561 ms 179728 KB Output is correct
17 Correct 540 ms 179872 KB Output is correct
18 Correct 561 ms 179780 KB Output is correct
19 Correct 565 ms 179792 KB Output is correct
20 Correct 536 ms 179780 KB Output is correct
21 Correct 553 ms 179876 KB Output is correct
22 Correct 619 ms 179908 KB Output is correct
23 Correct 834 ms 179908 KB Output is correct
24 Correct 996 ms 179924 KB Output is correct
25 Correct 514 ms 179024 KB Output is correct
26 Correct 559 ms 179732 KB Output is correct
27 Correct 525 ms 179908 KB Output is correct
28 Correct 515 ms 179912 KB Output is correct
29 Correct 582 ms 180020 KB Output is correct
30 Correct 676 ms 179908 KB Output is correct
31 Correct 666 ms 179920 KB Output is correct
32 Correct 975 ms 179852 KB Output is correct
33 Correct 1002 ms 179668 KB Output is correct
34 Correct 1422 ms 179776 KB Output is correct
35 Correct 835 ms 179804 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4044 KB Output is correct
2 Correct 4902 ms 1428768 KB Output is correct
3 Correct 5877 ms 1428884 KB Output is correct
4 Correct 5524 ms 1428892 KB Output is correct
5 Correct 4461 ms 1428968 KB Output is correct
6 Correct 4490 ms 1428848 KB Output is correct
7 Correct 4535 ms 1428848 KB Output is correct
8 Correct 5 ms 4044 KB Output is correct
9 Correct 561 ms 179760 KB Output is correct
10 Correct 483 ms 179908 KB Output is correct
11 Correct 541 ms 179908 KB Output is correct
12 Correct 493 ms 179792 KB Output is correct
13 Correct 577 ms 179780 KB Output is correct
14 Correct 560 ms 179884 KB Output is correct
15 Correct 551 ms 179924 KB Output is correct
16 Correct 485 ms 179780 KB Output is correct
17 Correct 545 ms 179808 KB Output is correct
18 Correct 757 ms 179800 KB Output is correct
19 Correct 1016 ms 179760 KB Output is correct
20 Correct 676 ms 179792 KB Output is correct
21 Correct 6 ms 4044 KB Output is correct
22 Correct 521 ms 179780 KB Output is correct
23 Correct 561 ms 179728 KB Output is correct
24 Correct 540 ms 179872 KB Output is correct
25 Correct 561 ms 179780 KB Output is correct
26 Correct 565 ms 179792 KB Output is correct
27 Correct 536 ms 179780 KB Output is correct
28 Correct 553 ms 179876 KB Output is correct
29 Correct 619 ms 179908 KB Output is correct
30 Correct 834 ms 179908 KB Output is correct
31 Correct 996 ms 179924 KB Output is correct
32 Correct 514 ms 179024 KB Output is correct
33 Correct 559 ms 179732 KB Output is correct
34 Correct 525 ms 179908 KB Output is correct
35 Correct 515 ms 179912 KB Output is correct
36 Correct 582 ms 180020 KB Output is correct
37 Correct 676 ms 179908 KB Output is correct
38 Correct 666 ms 179920 KB Output is correct
39 Correct 975 ms 179852 KB Output is correct
40 Correct 1002 ms 179668 KB Output is correct
41 Correct 1422 ms 179776 KB Output is correct
42 Correct 835 ms 179804 KB Output is correct
43 Correct 1 ms 460 KB Output is correct
44 Correct 5 ms 4044 KB Output is correct
45 Correct 5361 ms 1428960 KB Output is correct
46 Correct 4245 ms 1429008 KB Output is correct
47 Correct 4045 ms 1428892 KB Output is correct
48 Correct 3910 ms 1428804 KB Output is correct
49 Correct 5696 ms 1428940 KB Output is correct
50 Correct 4275 ms 1428888 KB Output is correct
51 Correct 3854 ms 1428796 KB Output is correct
52 Correct 4187 ms 1428800 KB Output is correct
53 Execution timed out 7170 ms 1272228 KB Time limit exceeded
54 Halted 0 ms 0 KB -