oj.uz

Submission #887562

# Submission time Handle Problem Language Result Execution time Memory
887562 2023-12-14T18:32:43 Z abcvuitunggio Dungeons Game (IOI21_dungeons) C++17
100 / 100
 4863 ms 1341444 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],mn[400001][24][sz],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()*32);
    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]=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];
                if (k<sz)
                    mn[i][j][k]=min(mn[i][j-1][k],mn[u][j-1][k]-sum[i][j-1][k]);
                else
                    mx[i][j]=max(mx[i][j-1],mx[u][j-1]-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])){
                    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 85 ms 264632 KB Output is correct
2 Correct 77 ms 264528 KB Output is correct
3 Correct 76 ms 270012 KB Output is correct
4 Correct 282 ms 398932 KB Output is correct
5 Correct 78 ms 269860 KB Output is correct
6 Correct 307 ms 398864 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 267344 KB Output is correct
2 Correct 2815 ms 1331964 KB Output is correct
3 Correct 2751 ms 1336300 KB Output is correct
4 Correct 2571 ms 1337848 KB Output is correct
5 Correct 2339 ms 1338824 KB Output is correct
6 Correct 2676 ms 1337840 KB Output is correct
7 Correct 2562 ms 1336544 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 267344 KB Output is correct
2 Correct 375 ms 400496 KB Output is correct
3 Correct 398 ms 400580 KB Output is correct
4 Correct 337 ms 400108 KB Output is correct
5 Correct 326 ms 399896 KB Output is correct
6 Correct 392 ms 400452 KB Output is correct
7 Correct 380 ms 400208 KB Output is correct
8 Correct 331 ms 400080 KB Output is correct
9 Correct 261 ms 399984 KB Output is correct
10 Correct 336 ms 399952 KB Output is correct
11 Correct 422 ms 400236 KB Output is correct
12 Correct 520 ms 400300 KB Output is correct
13 Correct 445 ms 400240 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 267344 KB Output is correct
2 Correct 375 ms 400496 KB Output is correct
3 Correct 398 ms 400580 KB Output is correct
4 Correct 337 ms 400108 KB Output is correct
5 Correct 326 ms 399896 KB Output is correct
6 Correct 392 ms 400452 KB Output is correct
7 Correct 380 ms 400208 KB Output is correct
8 Correct 331 ms 400080 KB Output is correct
9 Correct 261 ms 399984 KB Output is correct
10 Correct 336 ms 399952 KB Output is correct
11 Correct 422 ms 400236 KB Output is correct
12 Correct 520 ms 400300 KB Output is correct
13 Correct 445 ms 400240 KB Output is correct
14 Correct 79 ms 267344 KB Output is correct
15 Correct 381 ms 400364 KB Output is correct
16 Correct 390 ms 400212 KB Output is correct
17 Correct 395 ms 399952 KB Output is correct
18 Correct 374 ms 400112 KB Output is correct
19 Correct 387 ms 400464 KB Output is correct
20 Correct 397 ms 400128 KB Output is correct
21 Correct 406 ms 400304 KB Output is correct
22 Correct 477 ms 400208 KB Output is correct
23 Correct 368 ms 400208 KB Output is correct
24 Correct 501 ms 400236 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 267344 KB Output is correct
2 Correct 375 ms 400496 KB Output is correct
3 Correct 398 ms 400580 KB Output is correct
4 Correct 337 ms 400108 KB Output is correct
5 Correct 326 ms 399896 KB Output is correct
6 Correct 392 ms 400452 KB Output is correct
7 Correct 380 ms 400208 KB Output is correct
8 Correct 331 ms 400080 KB Output is correct
9 Correct 261 ms 399984 KB Output is correct
10 Correct 336 ms 399952 KB Output is correct
11 Correct 422 ms 400236 KB Output is correct
12 Correct 520 ms 400300 KB Output is correct
13 Correct 445 ms 400240 KB Output is correct
14 Correct 79 ms 267344 KB Output is correct
15 Correct 381 ms 400364 KB Output is correct
16 Correct 390 ms 400212 KB Output is correct
17 Correct 395 ms 399952 KB Output is correct
18 Correct 374 ms 400112 KB Output is correct
19 Correct 387 ms 400464 KB Output is correct
20 Correct 397 ms 400128 KB Output is correct
21 Correct 406 ms 400304 KB Output is correct
22 Correct 477 ms 400208 KB Output is correct
23 Correct 368 ms 400208 KB Output is correct
24 Correct 501 ms 400236 KB Output is correct
25 Correct 348 ms 399440 KB Output is correct
26 Correct 392 ms 400708 KB Output is correct
27 Correct 383 ms 399952 KB Output is correct
28 Correct 382 ms 399976 KB Output is correct
29 Correct 422 ms 400488 KB Output is correct
30 Correct 405 ms 400232 KB Output is correct
31 Correct 430 ms 399884 KB Output is correct
32 Correct 476 ms 400108 KB Output is correct
33 Correct 1233 ms 402744 KB Output is correct
34 Correct 1028 ms 404192 KB Output is correct
35 Correct 596 ms 404184 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 267344 KB Output is correct
2 Correct 2815 ms 1331964 KB Output is correct
3 Correct 2751 ms 1336300 KB Output is correct
4 Correct 2571 ms 1337848 KB Output is correct
5 Correct 2339 ms 1338824 KB Output is correct
6 Correct 2676 ms 1337840 KB Output is correct
7 Correct 2562 ms 1336544 KB Output is correct
8 Correct 79 ms 267344 KB Output is correct
9 Correct 375 ms 400496 KB Output is correct
10 Correct 398 ms 400580 KB Output is correct
11 Correct 337 ms 400108 KB Output is correct
12 Correct 326 ms 399896 KB Output is correct
13 Correct 392 ms 400452 KB Output is correct
14 Correct 380 ms 400208 KB Output is correct
15 Correct 331 ms 400080 KB Output is correct
16 Correct 261 ms 399984 KB Output is correct
17 Correct 336 ms 399952 KB Output is correct
18 Correct 422 ms 400236 KB Output is correct
19 Correct 520 ms 400300 KB Output is correct
20 Correct 445 ms 400240 KB Output is correct
21 Correct 79 ms 267344 KB Output is correct
22 Correct 381 ms 400364 KB Output is correct
23 Correct 390 ms 400212 KB Output is correct
24 Correct 395 ms 399952 KB Output is correct
25 Correct 374 ms 400112 KB Output is correct
26 Correct 387 ms 400464 KB Output is correct
27 Correct 397 ms 400128 KB Output is correct
28 Correct 406 ms 400304 KB Output is correct
29 Correct 477 ms 400208 KB Output is correct
30 Correct 368 ms 400208 KB Output is correct
31 Correct 501 ms 400236 KB Output is correct
32 Correct 348 ms 399440 KB Output is correct
33 Correct 392 ms 400708 KB Output is correct
34 Correct 383 ms 399952 KB Output is correct
35 Correct 382 ms 399976 KB Output is correct
36 Correct 422 ms 400488 KB Output is correct
37 Correct 405 ms 400232 KB Output is correct
38 Correct 430 ms 399884 KB Output is correct
39 Correct 476 ms 400108 KB Output is correct
40 Correct 1233 ms 402744 KB Output is correct
41 Correct 1028 ms 404192 KB Output is correct
42 Correct 596 ms 404184 KB Output is correct
43 Correct 30 ms 268608 KB Output is correct
44 Correct 32 ms 272980 KB Output is correct
45 Correct 2530 ms 1334392 KB Output is correct
46 Correct 2418 ms 1336836 KB Output is correct
47 Correct 2495 ms 1337836 KB Output is correct
48 Correct 2184 ms 1339524 KB Output is correct
49 Correct 2542 ms 1341444 KB Output is correct
50 Correct 2484 ms 1340152 KB Output is correct
51 Correct 2169 ms 1340548 KB Output is correct
52 Correct 2447 ms 1338736 KB Output is correct
53 Correct 3282 ms 1338876 KB Output is correct
54 Correct 3798 ms 1340148 KB Output is correct
55 Correct 3681 ms 1339792 KB Output is correct
56 Correct 4226 ms 1339768 KB Output is correct
57 Correct 4490 ms 1340208 KB Output is correct
58 Correct 4598 ms 1340164 KB Output is correct
59 Correct 4536 ms 1341048 KB Output is correct
60 Correct 4863 ms 1340276 KB Output is correct
61 Correct 4778 ms 1340464 KB Output is correct