oj.uz

Submission #879802

# Submission time Handle Problem Language Result Execution time Memory
879802 2023-11-28T07:12:48 Z abcvuitunggio Dungeons Game (IOI21_dungeons) C++17
100 / 100
 6275 ms 1869620 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int sz=6;
const long long INF=1e18;
int nxt[400001][24][sz+1];
long long mx[400001][24][sz+1],mn[400001][24][sz+1],sum[400001][24][sz+1];
vector <int> S,P,ve={1};
void init(int n, vector <int> s, vector <int> p, vector <int> w, vector <int> l){
    S=s;
    P=p;
    for (int i=1;i<sz;i++)
        ve.push_back(ve.back()*15);
    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[i][0][j]=w[i];
                sum[i][0][j]=s[i];
                mn[i][0][j]=INF;
            }
            else{
                nxt[i][0][j]=l[i];
                sum[i][0][j]=p[i];
                mn[i][0][j]=s[i];
            }
        nxt[i][0][sz]=w[i];
        mx[i][0][sz]=s[i];
        sum[i][0][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[i][j-1][k]==-1)
                    continue;
                int u=nxt[i][j-1][k];
                nxt[i][j][k]=nxt[u][j-1][k];
                mx[i][j][k]=max(mx[i][j-1][k],mx[u][j-1][k]-sum[i][j-1][k]);
                mn[i][j][k]=min(mn[i][j-1][k],mn[u][j-1][k]-sum[i][j-1][k]);
                sum[i][j][k]=sum[i][j-1][k]+sum[u][j-1][k];
            }
    }
}
long long simulate(int x, int Z){
    int b=0;
    long long z=Z;
    while (nxt[x][0][0]!=-1){
        int j=(b?upper_bound(ve.begin(),ve.end(),z)-ve.begin()-1:sz);
        for (int i=23;i>=0;i--)
            if (nxt[x][i][j]!=-1)
                if ((b&&z<mn[x][i][j])||(!b&&z>=mx[x][i][j])){
                    z+=sum[x][i][j];
                    x=nxt[x][i][j];
                }
        b^=1;
    }
	return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 269392 KB Output is correct
2 Correct 30 ms 269392 KB Output is correct
3 Correct 34 ms 277844 KB Output is correct
4 Correct 269 ms 469692 KB Output is correct
5 Correct 39 ms 277956 KB Output is correct
6 Correct 243 ms 469696 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 273868 KB Output is correct
2 Correct 2949 ms 1864020 KB Output is correct
3 Correct 2972 ms 1864272 KB Output is correct
4 Correct 2501 ms 1864660 KB Output is correct
5 Correct 2461 ms 1864788 KB Output is correct
6 Correct 2891 ms 1864380 KB Output is correct
7 Correct 2450 ms 1862996 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 273736 KB Output is correct
2 Correct 308 ms 471124 KB Output is correct
3 Correct 315 ms 471116 KB Output is correct
4 Correct 255 ms 470632 KB Output is correct
5 Correct 247 ms 470396 KB Output is correct
6 Correct 313 ms 470592 KB Output is correct
7 Correct 310 ms 470612 KB Output is correct
8 Correct 256 ms 470236 KB Output is correct
9 Correct 195 ms 470432 KB Output is correct
10 Correct 262 ms 470100 KB Output is correct
11 Correct 321 ms 470688 KB Output is correct
12 Correct 482 ms 470616 KB Output is correct
13 Correct 412 ms 470480 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 273736 KB Output is correct
2 Correct 308 ms 471124 KB Output is correct
3 Correct 315 ms 471116 KB Output is correct
4 Correct 255 ms 470632 KB Output is correct
5 Correct 247 ms 470396 KB Output is correct
6 Correct 313 ms 470592 KB Output is correct
7 Correct 310 ms 470612 KB Output is correct
8 Correct 256 ms 470236 KB Output is correct
9 Correct 195 ms 470432 KB Output is correct
10 Correct 262 ms 470100 KB Output is correct
11 Correct 321 ms 470688 KB Output is correct
12 Correct 482 ms 470616 KB Output is correct
13 Correct 412 ms 470480 KB Output is correct
14 Correct 33 ms 273744 KB Output is correct
15 Correct 302 ms 470828 KB Output is correct
16 Correct 316 ms 471056 KB Output is correct
17 Correct 300 ms 470548 KB Output is correct
18 Correct 280 ms 470896 KB Output is correct
19 Correct 320 ms 470696 KB Output is correct
20 Correct 300 ms 470484 KB Output is correct
21 Correct 296 ms 470564 KB Output is correct
22 Correct 329 ms 470568 KB Output is correct
23 Correct 328 ms 470612 KB Output is correct
24 Correct 494 ms 470680 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 273736 KB Output is correct
2 Correct 308 ms 471124 KB Output is correct
3 Correct 315 ms 471116 KB Output is correct
4 Correct 255 ms 470632 KB Output is correct
5 Correct 247 ms 470396 KB Output is correct
6 Correct 313 ms 470592 KB Output is correct
7 Correct 310 ms 470612 KB Output is correct
8 Correct 256 ms 470236 KB Output is correct
9 Correct 195 ms 470432 KB Output is correct
10 Correct 262 ms 470100 KB Output is correct
11 Correct 321 ms 470688 KB Output is correct
12 Correct 482 ms 470616 KB Output is correct
13 Correct 412 ms 470480 KB Output is correct
14 Correct 33 ms 273744 KB Output is correct
15 Correct 302 ms 470828 KB Output is correct
16 Correct 316 ms 471056 KB Output is correct
17 Correct 300 ms 470548 KB Output is correct
18 Correct 280 ms 470896 KB Output is correct
19 Correct 320 ms 470696 KB Output is correct
20 Correct 300 ms 470484 KB Output is correct
21 Correct 296 ms 470564 KB Output is correct
22 Correct 329 ms 470568 KB Output is correct
23 Correct 328 ms 470612 KB Output is correct
24 Correct 494 ms 470680 KB Output is correct
25 Correct 270 ms 470076 KB Output is correct
26 Correct 332 ms 471144 KB Output is correct
27 Correct 310 ms 470440 KB Output is correct
28 Correct 303 ms 470440 KB Output is correct
29 Correct 330 ms 471120 KB Output is correct
30 Correct 343 ms 470880 KB Output is correct
31 Correct 368 ms 470440 KB Output is correct
32 Correct 418 ms 470356 KB Output is correct
33 Correct 1203 ms 470760 KB Output is correct
34 Correct 1111 ms 470356 KB Output is correct
35 Correct 798 ms 470600 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 273868 KB Output is correct
2 Correct 2949 ms 1864020 KB Output is correct
3 Correct 2972 ms 1864272 KB Output is correct
4 Correct 2501 ms 1864660 KB Output is correct
5 Correct 2461 ms 1864788 KB Output is correct
6 Correct 2891 ms 1864380 KB Output is correct
7 Correct 2450 ms 1862996 KB Output is correct
8 Correct 33 ms 273736 KB Output is correct
9 Correct 308 ms 471124 KB Output is correct
10 Correct 315 ms 471116 KB Output is correct
11 Correct 255 ms 470632 KB Output is correct
12 Correct 247 ms 470396 KB Output is correct
13 Correct 313 ms 470592 KB Output is correct
14 Correct 310 ms 470612 KB Output is correct
15 Correct 256 ms 470236 KB Output is correct
16 Correct 195 ms 470432 KB Output is correct
17 Correct 262 ms 470100 KB Output is correct
18 Correct 321 ms 470688 KB Output is correct
19 Correct 482 ms 470616 KB Output is correct
20 Correct 412 ms 470480 KB Output is correct
21 Correct 33 ms 273744 KB Output is correct
22 Correct 302 ms 470828 KB Output is correct
23 Correct 316 ms 471056 KB Output is correct
24 Correct 300 ms 470548 KB Output is correct
25 Correct 280 ms 470896 KB Output is correct
26 Correct 320 ms 470696 KB Output is correct
27 Correct 300 ms 470484 KB Output is correct
28 Correct 296 ms 470564 KB Output is correct
29 Correct 329 ms 470568 KB Output is correct
30 Correct 328 ms 470612 KB Output is correct
31 Correct 494 ms 470680 KB Output is correct
32 Correct 270 ms 470076 KB Output is correct
33 Correct 332 ms 471144 KB Output is correct
34 Correct 310 ms 470440 KB Output is correct
35 Correct 303 ms 470440 KB Output is correct
36 Correct 330 ms 471120 KB Output is correct
37 Correct 343 ms 470880 KB Output is correct
38 Correct 368 ms 470440 KB Output is correct
39 Correct 418 ms 470356 KB Output is correct
40 Correct 1203 ms 470760 KB Output is correct
41 Correct 1111 ms 470356 KB Output is correct
42 Correct 798 ms 470600 KB Output is correct
43 Correct 31 ms 269404 KB Output is correct
44 Correct 33 ms 273748 KB Output is correct
45 Correct 3055 ms 1868380 KB Output is correct
46 Correct 2921 ms 1865044 KB Output is correct
47 Correct 3053 ms 1865044 KB Output is correct
48 Correct 2472 ms 1867608 KB Output is correct
49 Correct 3109 ms 1869620 KB Output is correct
50 Correct 2876 ms 1867100 KB Output is correct
51 Correct 2421 ms 1867384 KB Output is correct
52 Correct 2900 ms 1865276 KB Output is correct
53 Correct 4612 ms 1865532 KB Output is correct
54 Correct 4228 ms 1867092 KB Output is correct
55 Correct 4070 ms 1866188 KB Output is correct
56 Correct 6126 ms 1866476 KB Output is correct
57 Correct 5159 ms 1866808 KB Output is correct
58 Correct 5493 ms 1866836 KB Output is correct
59 Correct 5381 ms 1867072 KB Output is correct
60 Correct 6275 ms 1866396 KB Output is correct
61 Correct 6121 ms 1865784 KB Output is correct