oj.uz

Submission #929116

# Submission time Handle Problem Language Result Execution time Memory
929116 2024-02-17T17:42:26 Z abcvuitunggio Dungeons Game (IOI21_dungeons) C++17
100 / 100
 2609 ms 1921852 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int base=6,sz=9,lim=1e7;
const long long INF=1e18;
int N,nxt[24][400001][sz+1],lg[lim+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=2;i<=lim;i++)
        lg[i]=lg[i/2]+1;
    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=(b?lg[max(lim-z,0LL)]: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 119 ms 515660 KB Output is correct
2 Correct 64 ms 519840 KB Output is correct
3 Correct 69 ms 532348 KB Output is correct
4 Correct 160 ms 704492 KB Output is correct
5 Correct 66 ms 532308 KB Output is correct
6 Correct 140 ms 704696 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 530132 KB Output is correct
2 Correct 1103 ms 1917816 KB Output is correct
3 Correct 997 ms 1921740 KB Output is correct
4 Correct 748 ms 1921852 KB Output is correct
5 Correct 761 ms 1878504 KB Output is correct
6 Correct 1029 ms 1917512 KB Output is correct
7 Correct 645 ms 1921592 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 528212 KB Output is correct
2 Correct 190 ms 705364 KB Output is correct
3 Correct 187 ms 734164 KB Output is correct
4 Correct 157 ms 734032 KB Output is correct
5 Correct 159 ms 734148 KB Output is correct
6 Correct 207 ms 705384 KB Output is correct
7 Correct 192 ms 705364 KB Output is correct
8 Correct 162 ms 734176 KB Output is correct
9 Correct 177 ms 705472 KB Output is correct
10 Correct 155 ms 734156 KB Output is correct
11 Correct 227 ms 637700 KB Output is correct
12 Correct 372 ms 717704 KB Output is correct
13 Correct 234 ms 695044 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 528212 KB Output is correct
2 Correct 190 ms 705364 KB Output is correct
3 Correct 187 ms 734164 KB Output is correct
4 Correct 157 ms 734032 KB Output is correct
5 Correct 159 ms 734148 KB Output is correct
6 Correct 207 ms 705384 KB Output is correct
7 Correct 192 ms 705364 KB Output is correct
8 Correct 162 ms 734176 KB Output is correct
9 Correct 177 ms 705472 KB Output is correct
10 Correct 155 ms 734156 KB Output is correct
11 Correct 227 ms 637700 KB Output is correct
12 Correct 372 ms 717704 KB Output is correct
13 Correct 234 ms 695044 KB Output is correct
14 Correct 65 ms 528264 KB Output is correct
15 Correct 183 ms 705360 KB Output is correct
16 Correct 212 ms 705364 KB Output is correct
17 Correct 161 ms 731984 KB Output is correct
18 Correct 164 ms 731948 KB Output is correct
19 Correct 202 ms 705360 KB Output is correct
20 Correct 189 ms 734136 KB Output is correct
21 Correct 188 ms 734292 KB Output is correct
22 Correct 225 ms 633644 KB Output is correct
23 Correct 250 ms 717696 KB Output is correct
24 Correct 361 ms 717652 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 528212 KB Output is correct
2 Correct 190 ms 705364 KB Output is correct
3 Correct 187 ms 734164 KB Output is correct
4 Correct 157 ms 734032 KB Output is correct
5 Correct 159 ms 734148 KB Output is correct
6 Correct 207 ms 705384 KB Output is correct
7 Correct 192 ms 705364 KB Output is correct
8 Correct 162 ms 734176 KB Output is correct
9 Correct 177 ms 705472 KB Output is correct
10 Correct 155 ms 734156 KB Output is correct
11 Correct 227 ms 637700 KB Output is correct
12 Correct 372 ms 717704 KB Output is correct
13 Correct 234 ms 695044 KB Output is correct
14 Correct 65 ms 528264 KB Output is correct
15 Correct 183 ms 705360 KB Output is correct
16 Correct 212 ms 705364 KB Output is correct
17 Correct 161 ms 731984 KB Output is correct
18 Correct 164 ms 731948 KB Output is correct
19 Correct 202 ms 705360 KB Output is correct
20 Correct 189 ms 734136 KB Output is correct
21 Correct 188 ms 734292 KB Output is correct
22 Correct 225 ms 633644 KB Output is correct
23 Correct 250 ms 717696 KB Output is correct
24 Correct 361 ms 717652 KB Output is correct
25 Correct 155 ms 704808 KB Output is correct
26 Correct 198 ms 705496 KB Output is correct
27 Correct 189 ms 705360 KB Output is correct
28 Correct 185 ms 705872 KB Output is correct
29 Correct 234 ms 705292 KB Output is correct
30 Correct 197 ms 734036 KB Output is correct
31 Correct 209 ms 734032 KB Output is correct
32 Correct 327 ms 717600 KB Output is correct
33 Correct 876 ms 723752 KB Output is correct
34 Correct 1162 ms 725840 KB Output is correct
35 Correct 437 ms 717648 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 530132 KB Output is correct
2 Correct 1103 ms 1917816 KB Output is correct
3 Correct 997 ms 1921740 KB Output is correct
4 Correct 748 ms 1921852 KB Output is correct
5 Correct 761 ms 1878504 KB Output is correct
6 Correct 1029 ms 1917512 KB Output is correct
7 Correct 645 ms 1921592 KB Output is correct
8 Correct 68 ms 528212 KB Output is correct
9 Correct 190 ms 705364 KB Output is correct
10 Correct 187 ms 734164 KB Output is correct
11 Correct 157 ms 734032 KB Output is correct
12 Correct 159 ms 734148 KB Output is correct
13 Correct 207 ms 705384 KB Output is correct
14 Correct 192 ms 705364 KB Output is correct
15 Correct 162 ms 734176 KB Output is correct
16 Correct 177 ms 705472 KB Output is correct
17 Correct 155 ms 734156 KB Output is correct
18 Correct 227 ms 637700 KB Output is correct
19 Correct 372 ms 717704 KB Output is correct
20 Correct 234 ms 695044 KB Output is correct
21 Correct 65 ms 528264 KB Output is correct
22 Correct 183 ms 705360 KB Output is correct
23 Correct 212 ms 705364 KB Output is correct
24 Correct 161 ms 731984 KB Output is correct
25 Correct 164 ms 731948 KB Output is correct
26 Correct 202 ms 705360 KB Output is correct
27 Correct 189 ms 734136 KB Output is correct
28 Correct 188 ms 734292 KB Output is correct
29 Correct 225 ms 633644 KB Output is correct
30 Correct 250 ms 717696 KB Output is correct
31 Correct 361 ms 717652 KB Output is correct
32 Correct 155 ms 704808 KB Output is correct
33 Correct 198 ms 705496 KB Output is correct
34 Correct 189 ms 705360 KB Output is correct
35 Correct 185 ms 705872 KB Output is correct
36 Correct 234 ms 705292 KB Output is correct
37 Correct 197 ms 734036 KB Output is correct
38 Correct 209 ms 734032 KB Output is correct
39 Correct 327 ms 717600 KB Output is correct
40 Correct 876 ms 723752 KB Output is correct
41 Correct 1162 ms 725840 KB Output is correct
42 Correct 437 ms 717648 KB Output is correct
43 Correct 63 ms 517688 KB Output is correct
44 Correct 69 ms 528204 KB Output is correct
45 Correct 1109 ms 1878340 KB Output is correct
46 Correct 1028 ms 1878592 KB Output is correct
47 Correct 976 ms 1878408 KB Output is correct
48 Correct 779 ms 1917512 KB Output is correct
49 Correct 1166 ms 1878848 KB Output is correct
50 Correct 1092 ms 1917840 KB Output is correct
51 Correct 742 ms 1917412 KB Output is correct
52 Correct 1025 ms 1917504 KB Output is correct
53 Correct 2176 ms 1899092 KB Output is correct
54 Correct 1695 ms 1905208 KB Output is correct
55 Correct 1869 ms 1905212 KB Output is correct
56 Correct 2422 ms 1901148 KB Output is correct
57 Correct 2494 ms 1899200 KB Output is correct
58 Correct 2566 ms 1899480 KB Output is correct
59 Correct 2609 ms 1899112 KB Output is correct
60 Correct 2553 ms 1913544 KB Output is correct
61 Correct 2136 ms 1905212 KB Output is correct