oj.uz

답안 #929124

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
929124 2024-02-17T18:21:51 Z abcvuitunggio 던전 (IOI21_dungeons) C++17
100 / 100
 2881 ms 1335372 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int base=15,sz=7;
const long long INF=1e18;
int N,nxt[24][400001][sz];
long long mn[24][400001][sz],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;i++)
        ve.push_back(ve.back()*base);
    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]=INF;
            }
            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],mn[j-1][u][k]-sum[j-1][i][k]);
                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 (cur<sz){
        while (cur<sz&&ve[cur]<=z)
            cur++;
        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=23;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 7 is above array bounds of 'int [7]' [-Warray-bounds]
   26 |         nxt[0][i][sz]=w[i];
      |         ~~~~~~~~~~~~^

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 361044 KB Output is correct
2 Correct 39 ms 361048 KB Output is correct
3 Correct 41 ms 365360 KB Output is correct
4 Correct 104 ms 496980 KB Output is correct
5 Correct 41 ms 365188 KB Output is correct
6 Correct 92 ms 497036 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 363088 KB Output is correct
2 Correct 622 ms 1334908 KB Output is correct
3 Correct 584 ms 1335148 KB Output is correct
4 Correct 540 ms 1335104 KB Output is correct
5 Correct 586 ms 1335168 KB Output is correct
6 Correct 643 ms 1334832 KB Output is correct
7 Correct 531 ms 1334832 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 363092 KB Output is correct
2 Correct 159 ms 498004 KB Output is correct
3 Correct 142 ms 497632 KB Output is correct
4 Correct 111 ms 497748 KB Output is correct
5 Correct 111 ms 497648 KB Output is correct
6 Correct 148 ms 497908 KB Output is correct
7 Correct 125 ms 497744 KB Output is correct
8 Correct 117 ms 497744 KB Output is correct
9 Correct 123 ms 497628 KB Output is correct
10 Correct 126 ms 497716 KB Output is correct
11 Correct 138 ms 429908 KB Output is correct
12 Correct 241 ms 497744 KB Output is correct
13 Correct 182 ms 497748 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 363092 KB Output is correct
2 Correct 159 ms 498004 KB Output is correct
3 Correct 142 ms 497632 KB Output is correct
4 Correct 111 ms 497748 KB Output is correct
5 Correct 111 ms 497648 KB Output is correct
6 Correct 148 ms 497908 KB Output is correct
7 Correct 125 ms 497744 KB Output is correct
8 Correct 117 ms 497744 KB Output is correct
9 Correct 123 ms 497628 KB Output is correct
10 Correct 126 ms 497716 KB Output is correct
11 Correct 138 ms 429908 KB Output is correct
12 Correct 241 ms 497744 KB Output is correct
13 Correct 182 ms 497748 KB Output is correct
14 Correct 41 ms 363092 KB Output is correct
15 Correct 127 ms 497764 KB Output is correct
16 Correct 158 ms 497796 KB Output is correct
17 Correct 123 ms 497744 KB Output is correct
18 Correct 123 ms 497744 KB Output is correct
19 Correct 154 ms 497836 KB Output is correct
20 Correct 132 ms 497744 KB Output is correct
21 Correct 153 ms 497748 KB Output is correct
22 Correct 196 ms 417616 KB Output is correct
23 Correct 166 ms 497748 KB Output is correct
24 Correct 361 ms 497748 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 363092 KB Output is correct
2 Correct 159 ms 498004 KB Output is correct
3 Correct 142 ms 497632 KB Output is correct
4 Correct 111 ms 497748 KB Output is correct
5 Correct 111 ms 497648 KB Output is correct
6 Correct 148 ms 497908 KB Output is correct
7 Correct 125 ms 497744 KB Output is correct
8 Correct 117 ms 497744 KB Output is correct
9 Correct 123 ms 497628 KB Output is correct
10 Correct 126 ms 497716 KB Output is correct
11 Correct 138 ms 429908 KB Output is correct
12 Correct 241 ms 497744 KB Output is correct
13 Correct 182 ms 497748 KB Output is correct
14 Correct 41 ms 363092 KB Output is correct
15 Correct 127 ms 497764 KB Output is correct
16 Correct 158 ms 497796 KB Output is correct
17 Correct 123 ms 497744 KB Output is correct
18 Correct 123 ms 497744 KB Output is correct
19 Correct 154 ms 497836 KB Output is correct
20 Correct 132 ms 497744 KB Output is correct
21 Correct 153 ms 497748 KB Output is correct
22 Correct 196 ms 417616 KB Output is correct
23 Correct 166 ms 497748 KB Output is correct
24 Correct 361 ms 497748 KB Output is correct
25 Correct 95 ms 496980 KB Output is correct
26 Correct 150 ms 497820 KB Output is correct
27 Correct 137 ms 497744 KB Output is correct
28 Correct 149 ms 497632 KB Output is correct
29 Correct 163 ms 497748 KB Output is correct
30 Correct 144 ms 497748 KB Output is correct
31 Correct 164 ms 497664 KB Output is correct
32 Correct 208 ms 497644 KB Output is correct
33 Correct 591 ms 497744 KB Output is correct
34 Correct 1025 ms 498004 KB Output is correct
35 Correct 556 ms 497744 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 363088 KB Output is correct
2 Correct 622 ms 1334908 KB Output is correct
3 Correct 584 ms 1335148 KB Output is correct
4 Correct 540 ms 1335104 KB Output is correct
5 Correct 586 ms 1335168 KB Output is correct
6 Correct 643 ms 1334832 KB Output is correct
7 Correct 531 ms 1334832 KB Output is correct
8 Correct 42 ms 363092 KB Output is correct
9 Correct 159 ms 498004 KB Output is correct
10 Correct 142 ms 497632 KB Output is correct
11 Correct 111 ms 497748 KB Output is correct
12 Correct 111 ms 497648 KB Output is correct
13 Correct 148 ms 497908 KB Output is correct
14 Correct 125 ms 497744 KB Output is correct
15 Correct 117 ms 497744 KB Output is correct
16 Correct 123 ms 497628 KB Output is correct
17 Correct 126 ms 497716 KB Output is correct
18 Correct 138 ms 429908 KB Output is correct
19 Correct 241 ms 497744 KB Output is correct
20 Correct 182 ms 497748 KB Output is correct
21 Correct 41 ms 363092 KB Output is correct
22 Correct 127 ms 497764 KB Output is correct
23 Correct 158 ms 497796 KB Output is correct
24 Correct 123 ms 497744 KB Output is correct
25 Correct 123 ms 497744 KB Output is correct
26 Correct 154 ms 497836 KB Output is correct
27 Correct 132 ms 497744 KB Output is correct
28 Correct 153 ms 497748 KB Output is correct
29 Correct 196 ms 417616 KB Output is correct
30 Correct 166 ms 497748 KB Output is correct
31 Correct 361 ms 497748 KB Output is correct
32 Correct 95 ms 496980 KB Output is correct
33 Correct 150 ms 497820 KB Output is correct
34 Correct 137 ms 497744 KB Output is correct
35 Correct 149 ms 497632 KB Output is correct
36 Correct 163 ms 497748 KB Output is correct
37 Correct 144 ms 497748 KB Output is correct
38 Correct 164 ms 497664 KB Output is correct
39 Correct 208 ms 497644 KB Output is correct
40 Correct 591 ms 497744 KB Output is correct
41 Correct 1025 ms 498004 KB Output is correct
42 Correct 556 ms 497744 KB Output is correct
43 Correct 40 ms 361092 KB Output is correct
44 Correct 41 ms 363096 KB Output is correct
45 Correct 797 ms 1334932 KB Output is correct
46 Correct 656 ms 1335180 KB Output is correct
47 Correct 660 ms 1335372 KB Output is correct
48 Correct 610 ms 1334848 KB Output is correct
49 Correct 760 ms 1334860 KB Output is correct
50 Correct 602 ms 1335052 KB Output is correct
51 Correct 528 ms 1334912 KB Output is correct
52 Correct 603 ms 1335124 KB Output is correct
53 Correct 1464 ms 1335208 KB Output is correct
54 Correct 1295 ms 1334864 KB Output is correct
55 Correct 1603 ms 1335024 KB Output is correct
56 Correct 2343 ms 1335288 KB Output is correct
57 Correct 1747 ms 1334936 KB Output is correct
58 Correct 1985 ms 1334964 KB Output is correct
59 Correct 2019 ms 1335060 KB Output is correct
60 Correct 2881 ms 1335160 KB Output is correct
61 Correct 2624 ms 1334868 KB Output is correct