oj.uz

Submission #618044

# Submission time Handle Problem Language Result Execution time Memory
618044 2022-08-01T20:06:43 Z Soumya1 Dungeons Game (IOI21_dungeons) C++17
100 / 100
 2020 ms 1018460 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 400000;
const int lg2 = 20;
const int lg10 = 8;
const long long inf = 1e9;
int to[lg10][lg2][mxN];
int lim[lg10][lg2][mxN];
long long add[lg10][lg2][mxN];
int pw[lg10];
int n;
vector<int> s, p, w, l;
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
	n = _n, s = _s, p = _p, w = _w, l = _l;
	pw[0] = 1;
	for (int i = 1; i < lg10; i++) pw[i] = pw[i - 1] * 10;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < lg10; j++) {
			if (pw[j] >= s[i]) {
				to[j][0][i] = w[i];
				add[j][0][i] = s[i];
				lim[j][0][i] = inf;
			} else {
				to[j][0][i] = l[i];
				add[j][0][i] = p[i];
				lim[j][0][i] = s[i];
			}
		}
	}
	for (int i = 0; i < lg10; i++) {
		for (int j = 1; j < lg2; j++) {
			for (int k = 0; k < n; k++) {
				if (to[i][j - 1][k] == n) {
					to[i][j][k] = n;
					continue;
				}
				to[i][j][k] = to[i][j - 1][to[i][j - 1][k]];
				add[i][j][k] = add[i][j - 1][k] + add[i][j - 1][to[i][j - 1][k]];
				if (lim[i][j - 1][to[i][j - 1][k]] == inf) lim[i][j][k] = lim[i][j - 1][k];
				else lim[i][j][k] = min(1LL * lim[i][j - 1][k], max(0LL, 1LL * lim[i][j - 1][to[i][j - 1][k]] - add[i][j - 1][k]));	
			}
		}
	}
	return;
}

long long simulate(int x, int _z) {
	long long z = _z;
	while (x != n) {
		int c = 0;
		while (c + 1 < lg10 && pw[c + 1] <= z) c++;
		for (int j = lg2 - 1; j >= 0; j--) {
			if (lim[c][j][x] != inf && z >= lim[c][j][x]) continue;
			if (to[c][j][x] == n) continue;
			z += add[c][j][x];
			x = to[c][j][x];
		}
		if (x == n) break;
		if (z >= s[x]) {
			z += s[x];
			x = w[x];
		} else {
			z += p[x];
			x = l[x];
		}
	}
	return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2772 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 74 ms 98128 KB Output is correct
5 Correct 4 ms 6612 KB Output is correct
6 Correct 80 ms 98120 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5972 KB Output is correct
2 Correct 671 ms 1013880 KB Output is correct
3 Correct 673 ms 1016756 KB Output is correct
4 Correct 802 ms 1010564 KB Output is correct
5 Correct 760 ms 891240 KB Output is correct
6 Correct 765 ms 1013268 KB Output is correct
7 Correct 722 ms 1016496 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5972 KB Output is correct
2 Correct 137 ms 124108 KB Output is correct
3 Correct 129 ms 129936 KB Output is correct
4 Correct 100 ms 115176 KB Output is correct
5 Correct 109 ms 112380 KB Output is correct
6 Correct 161 ms 124856 KB Output is correct
7 Correct 254 ms 124824 KB Output is correct
8 Correct 122 ms 114928 KB Output is correct
9 Correct 88 ms 73760 KB Output is correct
10 Correct 112 ms 114820 KB Output is correct
11 Correct 129 ms 114560 KB Output is correct
12 Correct 961 ms 127424 KB Output is correct
13 Correct 889 ms 121880 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5972 KB Output is correct
2 Correct 137 ms 124108 KB Output is correct
3 Correct 129 ms 129936 KB Output is correct
4 Correct 100 ms 115176 KB Output is correct
5 Correct 109 ms 112380 KB Output is correct
6 Correct 161 ms 124856 KB Output is correct
7 Correct 254 ms 124824 KB Output is correct
8 Correct 122 ms 114928 KB Output is correct
9 Correct 88 ms 73760 KB Output is correct
10 Correct 112 ms 114820 KB Output is correct
11 Correct 129 ms 114560 KB Output is correct
12 Correct 961 ms 127424 KB Output is correct
13 Correct 889 ms 121880 KB Output is correct
14 Correct 4 ms 5972 KB Output is correct
15 Correct 114 ms 125060 KB Output is correct
16 Correct 125 ms 125228 KB Output is correct
17 Correct 111 ms 130048 KB Output is correct
18 Correct 107 ms 130092 KB Output is correct
19 Correct 169 ms 124824 KB Output is correct
20 Correct 132 ms 130072 KB Output is correct
21 Correct 125 ms 130124 KB Output is correct
22 Correct 126 ms 106260 KB Output is correct
23 Correct 134 ms 121128 KB Output is correct
24 Correct 208 ms 121296 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5972 KB Output is correct
2 Correct 137 ms 124108 KB Output is correct
3 Correct 129 ms 129936 KB Output is correct
4 Correct 100 ms 115176 KB Output is correct
5 Correct 109 ms 112380 KB Output is correct
6 Correct 161 ms 124856 KB Output is correct
7 Correct 254 ms 124824 KB Output is correct
8 Correct 122 ms 114928 KB Output is correct
9 Correct 88 ms 73760 KB Output is correct
10 Correct 112 ms 114820 KB Output is correct
11 Correct 129 ms 114560 KB Output is correct
12 Correct 961 ms 127424 KB Output is correct
13 Correct 889 ms 121880 KB Output is correct
14 Correct 4 ms 5972 KB Output is correct
15 Correct 114 ms 125060 KB Output is correct
16 Correct 125 ms 125228 KB Output is correct
17 Correct 111 ms 130048 KB Output is correct
18 Correct 107 ms 130092 KB Output is correct
19 Correct 169 ms 124824 KB Output is correct
20 Correct 132 ms 130072 KB Output is correct
21 Correct 125 ms 130124 KB Output is correct
22 Correct 126 ms 106260 KB Output is correct
23 Correct 134 ms 121128 KB Output is correct
24 Correct 208 ms 121296 KB Output is correct
25 Correct 91 ms 124112 KB Output is correct
26 Correct 127 ms 125236 KB Output is correct
27 Correct 116 ms 124648 KB Output is correct
28 Correct 115 ms 124772 KB Output is correct
29 Correct 143 ms 125156 KB Output is correct
30 Correct 143 ms 130668 KB Output is correct
31 Correct 142 ms 130432 KB Output is correct
32 Correct 216 ms 121144 KB Output is correct
33 Correct 436 ms 127564 KB Output is correct
34 Correct 1047 ms 127816 KB Output is correct
35 Correct 387 ms 125364 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5972 KB Output is correct
2 Correct 671 ms 1013880 KB Output is correct
3 Correct 673 ms 1016756 KB Output is correct
4 Correct 802 ms 1010564 KB Output is correct
5 Correct 760 ms 891240 KB Output is correct
6 Correct 765 ms 1013268 KB Output is correct
7 Correct 722 ms 1016496 KB Output is correct
8 Correct 4 ms 5972 KB Output is correct
9 Correct 137 ms 124108 KB Output is correct
10 Correct 129 ms 129936 KB Output is correct
11 Correct 100 ms 115176 KB Output is correct
12 Correct 109 ms 112380 KB Output is correct
13 Correct 161 ms 124856 KB Output is correct
14 Correct 254 ms 124824 KB Output is correct
15 Correct 122 ms 114928 KB Output is correct
16 Correct 88 ms 73760 KB Output is correct
17 Correct 112 ms 114820 KB Output is correct
18 Correct 129 ms 114560 KB Output is correct
19 Correct 961 ms 127424 KB Output is correct
20 Correct 889 ms 121880 KB Output is correct
21 Correct 4 ms 5972 KB Output is correct
22 Correct 114 ms 125060 KB Output is correct
23 Correct 125 ms 125228 KB Output is correct
24 Correct 111 ms 130048 KB Output is correct
25 Correct 107 ms 130092 KB Output is correct
26 Correct 169 ms 124824 KB Output is correct
27 Correct 132 ms 130072 KB Output is correct
28 Correct 125 ms 130124 KB Output is correct
29 Correct 126 ms 106260 KB Output is correct
30 Correct 134 ms 121128 KB Output is correct
31 Correct 208 ms 121296 KB Output is correct
32 Correct 91 ms 124112 KB Output is correct
33 Correct 127 ms 125236 KB Output is correct
34 Correct 116 ms 124648 KB Output is correct
35 Correct 115 ms 124772 KB Output is correct
36 Correct 143 ms 125156 KB Output is correct
37 Correct 143 ms 130668 KB Output is correct
38 Correct 142 ms 130432 KB Output is correct
39 Correct 216 ms 121144 KB Output is correct
40 Correct 436 ms 127564 KB Output is correct
41 Correct 1047 ms 127816 KB Output is correct
42 Correct 387 ms 125364 KB Output is correct
43 Correct 1 ms 1876 KB Output is correct
44 Correct 4 ms 5972 KB Output is correct
45 Correct 960 ms 964072 KB Output is correct
46 Correct 740 ms 962912 KB Output is correct
47 Correct 735 ms 961724 KB Output is correct
48 Correct 754 ms 1018460 KB Output is correct
49 Correct 1014 ms 959748 KB Output is correct
50 Correct 683 ms 1016408 KB Output is correct
51 Correct 702 ms 1014820 KB Output is correct
52 Correct 699 ms 1015052 KB Output is correct
53 Correct 1283 ms 949060 KB Output is correct
54 Correct 1292 ms 991680 KB Output is correct
55 Correct 1761 ms 1001012 KB Output is correct
56 Correct 1461 ms 995932 KB Output is correct
57 Correct 1505 ms 991564 KB Output is correct
58 Correct 2020 ms 991464 KB Output is correct
59 Correct 1768 ms 991480 KB Output is correct
60 Correct 1361 ms 1013524 KB Output is correct
61 Correct 1260 ms 999524 KB Output is correct