oj.uz

Submission #929729

# Submission time Handle Problem Language Result Execution time Memory
929729 2024-02-18T07:44:33 Z abcvuitunggio Dungeons Game (IOI21_dungeons) C++17
100 / 100
 4306 ms 1835148 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int base=5,sz=12;
int N,nxt[24][400001][sz],mn[24][400001][sz];
long long sum[24][400001][sz];
vector <int> S,P,W,L,ve={1};
void init(int n, vector <int> s, vector <int> p, vector <int> w, vector <int> l){
    N=n,S=s,P=p,W=w,L=l;
    for (int i=1;i<sz-1;i++)
        ve.push_back(ve.back()*base);
    ve.push_back(10000001);
    memset(nxt,-1,sizeof(nxt));
    for (int i=0;i<n;i++){
        for (int j=0;j<sz;j++)
            if (s[i]<=ve[j]){
                nxt[0][i][j]=w[i];
                sum[0][i][j]=s[i];
                mn[0][i][j]=1e9;
            }
            else{
                nxt[0][i][j]=l[i];
                sum[0][i][j]=p[i];
                mn[0][i][j]=s[i];
            }
        nxt[0][i][sz]=w[i];
    }
    for (int j=1;j<24;j++){
        for (int i=0;i<n;i++)
            for (int k=0;k<sz;k++){
                if (nxt[j-1][i][k]==-1)
                    continue;
                int u=nxt[j-1][i][k];
                nxt[j][i][k]=nxt[j-1][u][k];
                mn[j][i][k]=min(mn[j-1][i][k],(int)max(mn[j-1][u][k]-sum[j-1][i][k],0LL));
                sum[j][i][k]=sum[j-1][i][k]+sum[j-1][u][k];
            }
    }
}
long long simulate(int x, int Z){
    int cur=0;
    long long z=Z;
    while (x<N){
        while (cur<sz&&ve[cur]<=z)
            cur++;
        if (cur==sz)
            break;
        int j=cur-1;
        for (int i=23;i>=0;i--)
            if (nxt[i][x][j]!=-1&&z<mn[i][x][j]){
                z+=sum[i][x][j];
                x=nxt[i][x][j];
            }
        if (x==N)
            break;
        if (z<S[x]){
            z+=P[x];
            x=L[x];
        }
        else{
            z+=S[x];
            x=W[x];
        }
    }
    int j=cur-1;
    for (int i=18;i>=0;i--)
        if (nxt[i][x][j]!=-1){
            z+=sum[i][x][j];
            x=nxt[i][x][j];
        }
    return z;
}

Compilation message

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:26:21: warning: array subscript 12 is above array bounds of 'int [12]' [-Warray-bounds]
   26 |         nxt[0][i][sz]=w[i];
      |         ~~~~~~~~~~~~^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 547920 KB Output is correct
2 Correct 71 ms 547924 KB Output is correct
3 Correct 77 ms 554308 KB Output is correct
4 Correct 188 ms 718688 KB Output is correct
5 Correct 75 ms 554156 KB Output is correct
6 Correct 192 ms 718716 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 549968 KB Output is correct
2 Correct 1505 ms 1823316 KB Output is correct
3 Correct 1506 ms 1830556 KB Output is correct
4 Correct 1083 ms 1831740 KB Output is correct
5 Correct 1378 ms 1831908 KB Output is correct
6 Correct 1396 ms 1830256 KB Output is correct
7 Correct 1148 ms 1828532 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 549968 KB Output is correct
2 Correct 247 ms 719352 KB Output is correct
3 Correct 224 ms 719512 KB Output is correct
4 Correct 190 ms 719440 KB Output is correct
5 Correct 190 ms 720464 KB Output is correct
6 Correct 279 ms 720648 KB Output is correct
7 Correct 277 ms 720724 KB Output is correct
8 Correct 214 ms 720468 KB Output is correct
9 Correct 249 ms 720392 KB Output is correct
10 Correct 190 ms 720208 KB Output is correct
11 Correct 292 ms 642896 KB Output is correct
12 Correct 495 ms 720772 KB Output is correct
13 Correct 255 ms 720724 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 549968 KB Output is correct
2 Correct 247 ms 719352 KB Output is correct
3 Correct 224 ms 719512 KB Output is correct
4 Correct 190 ms 719440 KB Output is correct
5 Correct 190 ms 720464 KB Output is correct
6 Correct 279 ms 720648 KB Output is correct
7 Correct 277 ms 720724 KB Output is correct
8 Correct 214 ms 720468 KB Output is correct
9 Correct 249 ms 720392 KB Output is correct
10 Correct 190 ms 720208 KB Output is correct
11 Correct 292 ms 642896 KB Output is correct
12 Correct 495 ms 720772 KB Output is correct
13 Correct 255 ms 720724 KB Output is correct
14 Correct 73 ms 550104 KB Output is correct
15 Correct 221 ms 720964 KB Output is correct
16 Correct 247 ms 720972 KB Output is correct
17 Correct 205 ms 720488 KB Output is correct
18 Correct 189 ms 720644 KB Output is correct
19 Correct 268 ms 720620 KB Output is correct
20 Correct 230 ms 720520 KB Output is correct
21 Correct 230 ms 720452 KB Output is correct
22 Correct 240 ms 628328 KB Output is correct
23 Correct 278 ms 721000 KB Output is correct
24 Correct 518 ms 720676 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 549968 KB Output is correct
2 Correct 247 ms 719352 KB Output is correct
3 Correct 224 ms 719512 KB Output is correct
4 Correct 190 ms 719440 KB Output is correct
5 Correct 190 ms 720464 KB Output is correct
6 Correct 279 ms 720648 KB Output is correct
7 Correct 277 ms 720724 KB Output is correct
8 Correct 214 ms 720468 KB Output is correct
9 Correct 249 ms 720392 KB Output is correct
10 Correct 190 ms 720208 KB Output is correct
11 Correct 292 ms 642896 KB Output is correct
12 Correct 495 ms 720772 KB Output is correct
13 Correct 255 ms 720724 KB Output is correct
14 Correct 73 ms 550104 KB Output is correct
15 Correct 221 ms 720964 KB Output is correct
16 Correct 247 ms 720972 KB Output is correct
17 Correct 205 ms 720488 KB Output is correct
18 Correct 189 ms 720644 KB Output is correct
19 Correct 268 ms 720620 KB Output is correct
20 Correct 230 ms 720520 KB Output is correct
21 Correct 230 ms 720452 KB Output is correct
22 Correct 240 ms 628328 KB Output is correct
23 Correct 278 ms 721000 KB Output is correct
24 Correct 518 ms 720676 KB Output is correct
25 Correct 162 ms 719956 KB Output is correct
26 Correct 223 ms 721140 KB Output is correct
27 Correct 221 ms 720488 KB Output is correct
28 Correct 277 ms 720648 KB Output is correct
29 Correct 258 ms 720980 KB Output is correct
30 Correct 291 ms 720568 KB Output is correct
31 Correct 280 ms 720376 KB Output is correct
32 Correct 519 ms 720632 KB Output is correct
33 Correct 827 ms 720660 KB Output is correct
34 Correct 1278 ms 720656 KB Output is correct
35 Correct 488 ms 720580 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 549968 KB Output is correct
2 Correct 1505 ms 1823316 KB Output is correct
3 Correct 1506 ms 1830556 KB Output is correct
4 Correct 1083 ms 1831740 KB Output is correct
5 Correct 1378 ms 1831908 KB Output is correct
6 Correct 1396 ms 1830256 KB Output is correct
7 Correct 1148 ms 1828532 KB Output is correct
8 Correct 72 ms 549968 KB Output is correct
9 Correct 247 ms 719352 KB Output is correct
10 Correct 224 ms 719512 KB Output is correct
11 Correct 190 ms 719440 KB Output is correct
12 Correct 190 ms 720464 KB Output is correct
13 Correct 279 ms 720648 KB Output is correct
14 Correct 277 ms 720724 KB Output is correct
15 Correct 214 ms 720468 KB Output is correct
16 Correct 249 ms 720392 KB Output is correct
17 Correct 190 ms 720208 KB Output is correct
18 Correct 292 ms 642896 KB Output is correct
19 Correct 495 ms 720772 KB Output is correct
20 Correct 255 ms 720724 KB Output is correct
21 Correct 73 ms 550104 KB Output is correct
22 Correct 221 ms 720964 KB Output is correct
23 Correct 247 ms 720972 KB Output is correct
24 Correct 205 ms 720488 KB Output is correct
25 Correct 189 ms 720644 KB Output is correct
26 Correct 268 ms 720620 KB Output is correct
27 Correct 230 ms 720520 KB Output is correct
28 Correct 230 ms 720452 KB Output is correct
29 Correct 240 ms 628328 KB Output is correct
30 Correct 278 ms 721000 KB Output is correct
31 Correct 518 ms 720676 KB Output is correct
32 Correct 162 ms 719956 KB Output is correct
33 Correct 223 ms 721140 KB Output is correct
34 Correct 221 ms 720488 KB Output is correct
35 Correct 277 ms 720648 KB Output is correct
36 Correct 258 ms 720980 KB Output is correct
37 Correct 291 ms 720568 KB Output is correct
38 Correct 280 ms 720376 KB Output is correct
39 Correct 519 ms 720632 KB Output is correct
40 Correct 827 ms 720660 KB Output is correct
41 Correct 1278 ms 720656 KB Output is correct
42 Correct 488 ms 720580 KB Output is correct
43 Correct 70 ms 548020 KB Output is correct
44 Correct 72 ms 550056 KB Output is correct
45 Correct 2073 ms 1835148 KB Output is correct
46 Correct 1685 ms 1830512 KB Output is correct
47 Correct 1711 ms 1830724 KB Output is correct
48 Correct 1367 ms 1832988 KB Output is correct
49 Correct 2198 ms 1835024 KB Output is correct
50 Correct 1549 ms 1832644 KB Output is correct
51 Correct 1202 ms 1833072 KB Output is correct
52 Correct 1400 ms 1830616 KB Output is correct
53 Correct 3164 ms 1831540 KB Output is correct
54 Correct 2172 ms 1832556 KB Output is correct
55 Correct 2655 ms 1831688 KB Output is correct
56 Correct 3691 ms 1832116 KB Output is correct
57 Correct 3722 ms 1832192 KB Output is correct
58 Correct 4306 ms 1832280 KB Output is correct
59 Correct 3885 ms 1832696 KB Output is correct
60 Correct 3185 ms 1831612 KB Output is correct
61 Correct 2692 ms 1831620 KB Output is correct