oj.uz

Submission #887569

# Submission time Handle Problem Language Result Execution time Memory
887569 2023-12-14T18:37:42 Z abcvuitunggio Dungeons Game (IOI21_dungeons) C++17
100 / 100
 4075 ms 1343744 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int base=32,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()*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[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,cur=0;
    long long z=Z;
    while (nxt[x][0][0]!=-1){
        while (cur<ve.size()&&ve[cur]<=z)
            cur++;
        int j=(b?cur-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;
}

Compilation message

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         while (cur<ve.size()&&ve[cur]<=z)
      |                ~~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 264528 KB Output is correct
2 Correct 51 ms 264672 KB Output is correct
3 Correct 47 ms 269908 KB Output is correct
4 Correct 295 ms 398996 KB Output is correct
5 Correct 34 ms 277076 KB Output is correct
6 Correct 312 ms 399092 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 273236 KB Output is correct
2 Correct 2373 ms 1331960 KB Output is correct
3 Correct 2441 ms 1338856 KB Output is correct
4 Correct 2808 ms 1339048 KB Output is correct
5 Correct 2052 ms 1340336 KB Output is correct
6 Correct 2447 ms 1338460 KB Output is correct
7 Correct 2861 ms 1336536 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 267348 KB Output is correct
2 Correct 422 ms 400488 KB Output is correct
3 Correct 435 ms 400708 KB Output is correct
4 Correct 402 ms 399964 KB Output is correct
5 Correct 357 ms 399956 KB Output is correct
6 Correct 289 ms 404320 KB Output is correct
7 Correct 425 ms 398976 KB Output is correct
8 Correct 377 ms 398728 KB Output is correct
9 Correct 302 ms 398724 KB Output is correct
10 Correct 386 ms 398736 KB Output is correct
11 Correct 433 ms 398988 KB Output is correct
12 Correct 472 ms 404312 KB Output is correct
13 Correct 532 ms 398988 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 267348 KB Output is correct
2 Correct 422 ms 400488 KB Output is correct
3 Correct 435 ms 400708 KB Output is correct
4 Correct 402 ms 399964 KB Output is correct
5 Correct 357 ms 399956 KB Output is correct
6 Correct 289 ms 404320 KB Output is correct
7 Correct 425 ms 398976 KB Output is correct
8 Correct 377 ms 398728 KB Output is correct
9 Correct 302 ms 398724 KB Output is correct
10 Correct 386 ms 398736 KB Output is correct
11 Correct 433 ms 398988 KB Output is correct
12 Correct 472 ms 404312 KB Output is correct
13 Correct 532 ms 398988 KB Output is correct
14 Correct 104 ms 265936 KB Output is correct
15 Correct 465 ms 399056 KB Output is correct
16 Correct 437 ms 399184 KB Output is correct
17 Correct 325 ms 404056 KB Output is correct
18 Correct 439 ms 398848 KB Output is correct
19 Correct 441 ms 398928 KB Output is correct
20 Correct 481 ms 398728 KB Output is correct
21 Correct 452 ms 398672 KB Output is correct
22 Correct 396 ms 404180 KB Output is correct
23 Correct 479 ms 398880 KB Output is correct
24 Correct 619 ms 398968 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 267348 KB Output is correct
2 Correct 422 ms 400488 KB Output is correct
3 Correct 435 ms 400708 KB Output is correct
4 Correct 402 ms 399964 KB Output is correct
5 Correct 357 ms 399956 KB Output is correct
6 Correct 289 ms 404320 KB Output is correct
7 Correct 425 ms 398976 KB Output is correct
8 Correct 377 ms 398728 KB Output is correct
9 Correct 302 ms 398724 KB Output is correct
10 Correct 386 ms 398736 KB Output is correct
11 Correct 433 ms 398988 KB Output is correct
12 Correct 472 ms 404312 KB Output is correct
13 Correct 532 ms 398988 KB Output is correct
14 Correct 104 ms 265936 KB Output is correct
15 Correct 465 ms 399056 KB Output is correct
16 Correct 437 ms 399184 KB Output is correct
17 Correct 325 ms 404056 KB Output is correct
18 Correct 439 ms 398848 KB Output is correct
19 Correct 441 ms 398928 KB Output is correct
20 Correct 481 ms 398728 KB Output is correct
21 Correct 452 ms 398672 KB Output is correct
22 Correct 396 ms 404180 KB Output is correct
23 Correct 479 ms 398880 KB Output is correct
24 Correct 619 ms 398968 KB Output is correct
25 Correct 396 ms 398160 KB Output is correct
26 Correct 443 ms 399232 KB Output is correct
27 Correct 434 ms 398728 KB Output is correct
28 Correct 440 ms 398720 KB Output is correct
29 Correct 471 ms 399240 KB Output is correct
30 Correct 328 ms 404076 KB Output is correct
31 Correct 501 ms 398876 KB Output is correct
32 Correct 526 ms 399960 KB Output is correct
33 Correct 1187 ms 403608 KB Output is correct
34 Correct 1076 ms 404052 KB Output is correct
35 Correct 606 ms 404180 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 273236 KB Output is correct
2 Correct 2373 ms 1331960 KB Output is correct
3 Correct 2441 ms 1338856 KB Output is correct
4 Correct 2808 ms 1339048 KB Output is correct
5 Correct 2052 ms 1340336 KB Output is correct
6 Correct 2447 ms 1338460 KB Output is correct
7 Correct 2861 ms 1336536 KB Output is correct
8 Correct 107 ms 267348 KB Output is correct
9 Correct 422 ms 400488 KB Output is correct
10 Correct 435 ms 400708 KB Output is correct
11 Correct 402 ms 399964 KB Output is correct
12 Correct 357 ms 399956 KB Output is correct
13 Correct 289 ms 404320 KB Output is correct
14 Correct 425 ms 398976 KB Output is correct
15 Correct 377 ms 398728 KB Output is correct
16 Correct 302 ms 398724 KB Output is correct
17 Correct 386 ms 398736 KB Output is correct
18 Correct 433 ms 398988 KB Output is correct
19 Correct 472 ms 404312 KB Output is correct
20 Correct 532 ms 398988 KB Output is correct
21 Correct 104 ms 265936 KB Output is correct
22 Correct 465 ms 399056 KB Output is correct
23 Correct 437 ms 399184 KB Output is correct
24 Correct 325 ms 404056 KB Output is correct
25 Correct 439 ms 398848 KB Output is correct
26 Correct 441 ms 398928 KB Output is correct
27 Correct 481 ms 398728 KB Output is correct
28 Correct 452 ms 398672 KB Output is correct
29 Correct 396 ms 404180 KB Output is correct
30 Correct 479 ms 398880 KB Output is correct
31 Correct 619 ms 398968 KB Output is correct
32 Correct 396 ms 398160 KB Output is correct
33 Correct 443 ms 399232 KB Output is correct
34 Correct 434 ms 398728 KB Output is correct
35 Correct 440 ms 398720 KB Output is correct
36 Correct 471 ms 399240 KB Output is correct
37 Correct 328 ms 404076 KB Output is correct
38 Correct 501 ms 398876 KB Output is correct
39 Correct 526 ms 399960 KB Output is correct
40 Correct 1187 ms 403608 KB Output is correct
41 Correct 1076 ms 404052 KB Output is correct
42 Correct 606 ms 404180 KB Output is correct
43 Correct 32 ms 268628 KB Output is correct
44 Correct 32 ms 272996 KB Output is correct
45 Correct 2586 ms 1341036 KB Output is correct
46 Correct 2457 ms 1338816 KB Output is correct
47 Correct 2433 ms 1339368 KB Output is correct
48 Correct 2134 ms 1341536 KB Output is correct
49 Correct 2782 ms 1343744 KB Output is correct
50 Correct 2528 ms 1341108 KB Output is correct
51 Correct 2113 ms 1341532 KB Output is correct
52 Correct 2458 ms 1339180 KB Output is correct
53 Correct 3442 ms 1340188 KB Output is correct
54 Correct 3416 ms 1341012 KB Output is correct
55 Correct 3350 ms 1340176 KB Output is correct
56 Correct 3552 ms 1339432 KB Output is correct
57 Correct 3583 ms 1340768 KB Output is correct
58 Correct 3450 ms 1340848 KB Output is correct
59 Correct 3386 ms 1341012 KB Output is correct
60 Correct 4075 ms 1340248 KB Output is correct
61 Correct 4008 ms 1340060 KB Output is correct