oj.uz

Submission #929118

# Submission time Handle Problem Language Result Execution time Memory
929118 2024-02-17T17:54:25 Z abcvuitunggio Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3684 ms 1319528 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int base=14,sz=6;
const long long INF=1e18;
int N,nxt[24][400001][sz+1];
long long mx[24][400001],mn[24][400001][sz],sum[24][400001][sz+1];
vector <int> S,P,ve={1};
void init(int n, vector <int> s, vector <int> p, vector <int> w, vector <int> l){
    N=n,S=s,P=p;
    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];
        mx[0][i]=sum[0][i][sz]=s[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];
                if (k<sz)
                    mn[j][i][k]=min(mn[j-1][i][k],mn[j-1][u][k]-sum[j-1][i][k]);
                else
                    mx[j][i]=max(mx[j-1][i],mx[j-1][u]-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 b=0,cur=0;
    long long z=Z;
    while (x<N){
        while (cur<sz&&ve[cur]<=z)
            cur++;
        int j=(b?cur-1:sz);
        for (int i=23;i>=0;i--)
            if (nxt[i][x][j]!=-1)
                if ((b&&z<mn[i][x][j])||(!b&&z>=mx[i][x])){
                    z+=sum[i][x][j];
                    x=nxt[i][x][j];
                }
        b^=1;
    }
    return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 365140 KB Output is correct
2 Correct 43 ms 369200 KB Output is correct
3 Correct 50 ms 377584 KB Output is correct
4 Correct 113 ms 498600 KB Output is correct
5 Correct 43 ms 377680 KB Output is correct
6 Correct 113 ms 498520 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 373440 KB Output is correct
2 Correct 665 ms 1319504 KB Output is correct
3 Correct 632 ms 1319476 KB Output is correct
4 Correct 623 ms 1319528 KB Output is correct
5 Correct 687 ms 1278484 KB Output is correct
6 Correct 678 ms 1319500 KB Output is correct
7 Correct 506 ms 1319508 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 371284 KB Output is correct
2 Correct 153 ms 499340 KB Output is correct
3 Correct 167 ms 521916 KB Output is correct
4 Correct 122 ms 526168 KB Output is correct
5 Correct 120 ms 522064 KB Output is correct
6 Correct 157 ms 499280 KB Output is correct
7 Correct 150 ms 499280 KB Output is correct
8 Correct 152 ms 526228 KB Output is correct
9 Correct 123 ms 499388 KB Output is correct
10 Correct 125 ms 526052 KB Output is correct
11 Correct 215 ms 443988 KB Output is correct
12 Correct 326 ms 507616 KB Output is correct
13 Correct 207 ms 491152 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 371284 KB Output is correct
2 Correct 153 ms 499340 KB Output is correct
3 Correct 167 ms 521916 KB Output is correct
4 Correct 122 ms 526168 KB Output is correct
5 Correct 120 ms 522064 KB Output is correct
6 Correct 157 ms 499280 KB Output is correct
7 Correct 150 ms 499280 KB Output is correct
8 Correct 152 ms 526228 KB Output is correct
9 Correct 123 ms 499388 KB Output is correct
10 Correct 125 ms 526052 KB Output is correct
11 Correct 215 ms 443988 KB Output is correct
12 Correct 326 ms 507616 KB Output is correct
13 Correct 207 ms 491152 KB Output is correct
14 Correct 53 ms 371284 KB Output is correct
15 Correct 144 ms 499284 KB Output is correct
16 Correct 169 ms 499284 KB Output is correct
17 Correct 122 ms 519824 KB Output is correct
18 Correct 129 ms 520008 KB Output is correct
19 Correct 164 ms 499288 KB Output is correct
20 Correct 146 ms 521924 KB Output is correct
21 Correct 186 ms 522068 KB Output is correct
22 Correct 247 ms 443972 KB Output is correct
23 Correct 201 ms 507476 KB Output is correct
24 Correct 280 ms 507632 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 371284 KB Output is correct
2 Correct 153 ms 499340 KB Output is correct
3 Correct 167 ms 521916 KB Output is correct
4 Correct 122 ms 526168 KB Output is correct
5 Correct 120 ms 522064 KB Output is correct
6 Correct 157 ms 499280 KB Output is correct
7 Correct 150 ms 499280 KB Output is correct
8 Correct 152 ms 526228 KB Output is correct
9 Correct 123 ms 499388 KB Output is correct
10 Correct 125 ms 526052 KB Output is correct
11 Correct 215 ms 443988 KB Output is correct
12 Correct 326 ms 507616 KB Output is correct
13 Correct 207 ms 491152 KB Output is correct
14 Correct 53 ms 371284 KB Output is correct
15 Correct 144 ms 499284 KB Output is correct
16 Correct 169 ms 499284 KB Output is correct
17 Correct 122 ms 519824 KB Output is correct
18 Correct 129 ms 520008 KB Output is correct
19 Correct 164 ms 499288 KB Output is correct
20 Correct 146 ms 521924 KB Output is correct
21 Correct 186 ms 522068 KB Output is correct
22 Correct 247 ms 443972 KB Output is correct
23 Correct 201 ms 507476 KB Output is correct
24 Correct 280 ms 507632 KB Output is correct
25 Correct 111 ms 498568 KB Output is correct
26 Correct 188 ms 499280 KB Output is correct
27 Correct 153 ms 499456 KB Output is correct
28 Correct 139 ms 499480 KB Output is correct
29 Correct 172 ms 499360 KB Output is correct
30 Correct 188 ms 525960 KB Output is correct
31 Correct 150 ms 526068 KB Output is correct
32 Correct 293 ms 507544 KB Output is correct
33 Correct 1440 ms 511624 KB Output is correct
34 Correct 1155 ms 513620 KB Output is correct
35 Correct 732 ms 507584 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 373440 KB Output is correct
2 Correct 665 ms 1319504 KB Output is correct
3 Correct 632 ms 1319476 KB Output is correct
4 Correct 623 ms 1319528 KB Output is correct
5 Correct 687 ms 1278484 KB Output is correct
6 Correct 678 ms 1319500 KB Output is correct
7 Correct 506 ms 1319508 KB Output is correct
8 Correct 43 ms 371284 KB Output is correct
9 Correct 153 ms 499340 KB Output is correct
10 Correct 167 ms 521916 KB Output is correct
11 Correct 122 ms 526168 KB Output is correct
12 Correct 120 ms 522064 KB Output is correct
13 Correct 157 ms 499280 KB Output is correct
14 Correct 150 ms 499280 KB Output is correct
15 Correct 152 ms 526228 KB Output is correct
16 Correct 123 ms 499388 KB Output is correct
17 Correct 125 ms 526052 KB Output is correct
18 Correct 215 ms 443988 KB Output is correct
19 Correct 326 ms 507616 KB Output is correct
20 Correct 207 ms 491152 KB Output is correct
21 Correct 53 ms 371284 KB Output is correct
22 Correct 144 ms 499284 KB Output is correct
23 Correct 169 ms 499284 KB Output is correct
24 Correct 122 ms 519824 KB Output is correct
25 Correct 129 ms 520008 KB Output is correct
26 Correct 164 ms 499288 KB Output is correct
27 Correct 146 ms 521924 KB Output is correct
28 Correct 186 ms 522068 KB Output is correct
29 Correct 247 ms 443972 KB Output is correct
30 Correct 201 ms 507476 KB Output is correct
31 Correct 280 ms 507632 KB Output is correct
32 Correct 111 ms 498568 KB Output is correct
33 Correct 188 ms 499280 KB Output is correct
34 Correct 153 ms 499456 KB Output is correct
35 Correct 139 ms 499480 KB Output is correct
36 Correct 172 ms 499360 KB Output is correct
37 Correct 188 ms 525960 KB Output is correct
38 Correct 150 ms 526068 KB Output is correct
39 Correct 293 ms 507544 KB Output is correct
40 Correct 1440 ms 511624 KB Output is correct
41 Correct 1155 ms 513620 KB Output is correct
42 Correct 732 ms 507584 KB Output is correct
43 Correct 45 ms 367172 KB Output is correct
44 Correct 43 ms 371280 KB Output is correct
45 Correct 997 ms 1278540 KB Output is correct
46 Correct 1002 ms 1278448 KB Output is correct
47 Correct 805 ms 1278748 KB Output is correct
48 Correct 768 ms 1319508 KB Output is correct
49 Correct 1050 ms 1278512 KB Output is correct
50 Correct 928 ms 1314492 KB Output is correct
51 Correct 647 ms 1315280 KB Output is correct
52 Correct 926 ms 1314384 KB Output is correct
53 Correct 2048 ms 1297164 KB Output is correct
54 Correct 2231 ms 1303120 KB Output is correct
55 Correct 1695 ms 1305172 KB Output is correct
56 Correct 2937 ms 1298972 KB Output is correct
57 Correct 2272 ms 1296960 KB Output is correct
58 Correct 2907 ms 1295576 KB Output is correct
59 Correct 2991 ms 1295460 KB Output is correct
60 Correct 3684 ms 1311296 KB Output is correct
61 Correct 3038 ms 1303384 KB Output is correct