oj.uz

Submission #797971

# Submission time Handle Problem Language Result Execution time Memory
797971 2023-07-30T08:10:47 Z iee Dungeons Game (IOI21_dungeons) C++17
100 / 100
 4635 ms 1790320 KB 
#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
constexpr int Base = 8, LN = 25, LS = 9, N = 4e5 + 5;
using ll = long long;
constexpr ll inf = 1e18;
int n;
int go[LS][N][LN];
ll lim[LS][N][LN], gain[LS][N][LN], pw[LS];
vector<int> s, p, win, lose;
void init(int _n, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
	n = _n, s = S, p = P, win = W, lose = L;
	for (int i = pw[0] = 1; i < LS; i++) {
		pw[i] = pw[i - 1] * Base;
	}
	for (int C = 0; C < LS; C++) {
		for (int i = 0; i < n; i++) {
			if (pw[C] >= s[i]) {
				if (win[i] == n) {
					go[C][i][0] = -1;
				} else {
					go[C][i][0] = win[i];
					gain[C][i][0] = s[i];
					lim[C][i][0] = inf;
				}
			} else {
				if (lose[i] == n) {
					go[C][i][0] = -1;
				} else {
					go[C][i][0] = lose[i];
					gain[C][i][0] = p[i];
					lim[C][i][0] = s[i];
				}
			}
		}
	}
	for (int C = 0; C < LS; C++) {
		for (int j = 1; j < LN; j++) {
			for (int i = 0; i < n; i++) {
				if (go[C][i][j - 1] == -1 || go[C][go[C][i][j - 1]][j - 1] == -1) {
					go[C][i][j] = -1;
					continue;
				}
				go[C][i][j] = go[C][go[C][i][j - 1]][j - 1];
				gain[C][i][j] = gain[C][i][j - 1] + gain[C][go[C][i][j - 1]][j - 1];
				lim[C][i][j] = min(lim[C][i][j - 1], lim[C][go[C][i][j - 1]][j - 1] - gain[C][i][j - 1]);
			}
		}
	}
}

long long simulate(int x, int z) {
	long long str = z, c = 0;
	while (x != n) {
		while (c + 1 < LS && pw[c + 1] <= str) c++;
		for (int i = LN - 1; i >= 0; i--) {
			if (go[c][x][i] == -1) continue;
			if (str < lim[c][x][i]) {
				str += gain[c][x][i];
				x = go[c][x][i];
			}
		}
		if (str >= s[x]) str += s[x], x = win[x];
		else str += p[x], x = lose[x];
	}
	return str;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 7 ms 9444 KB Output is correct
4 Correct 204 ms 224076 KB Output is correct
5 Correct 7 ms 9428 KB Output is correct
6 Correct 217 ms 223936 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4932 KB Output is correct
2 Correct 2851 ms 1783680 KB Output is correct
3 Correct 2735 ms 1784104 KB Output is correct
4 Correct 2683 ms 1783968 KB Output is correct
5 Correct 2367 ms 1783840 KB Output is correct
6 Correct 2899 ms 1783812 KB Output is correct
7 Correct 2605 ms 1783764 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 312 ms 225452 KB Output is correct
3 Correct 282 ms 225532 KB Output is correct
4 Correct 235 ms 224876 KB Output is correct
5 Correct 245 ms 224824 KB Output is correct
6 Correct 300 ms 225080 KB Output is correct
7 Correct 290 ms 225068 KB Output is correct
8 Correct 240 ms 224844 KB Output is correct
9 Correct 185 ms 224824 KB Output is correct
10 Correct 262 ms 224592 KB Output is correct
11 Correct 327 ms 225064 KB Output is correct
12 Correct 524 ms 225088 KB Output is correct
13 Correct 320 ms 205384 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 312 ms 225452 KB Output is correct
3 Correct 282 ms 225532 KB Output is correct
4 Correct 235 ms 224876 KB Output is correct
5 Correct 245 ms 224824 KB Output is correct
6 Correct 300 ms 225080 KB Output is correct
7 Correct 290 ms 225068 KB Output is correct
8 Correct 240 ms 224844 KB Output is correct
9 Correct 185 ms 224824 KB Output is correct
10 Correct 262 ms 224592 KB Output is correct
11 Correct 327 ms 225064 KB Output is correct
12 Correct 524 ms 225088 KB Output is correct
13 Correct 320 ms 205384 KB Output is correct
14 Correct 4 ms 4932 KB Output is correct
15 Correct 269 ms 225208 KB Output is correct
16 Correct 297 ms 225192 KB Output is correct
17 Correct 337 ms 224716 KB Output is correct
18 Correct 279 ms 224424 KB Output is correct
19 Correct 295 ms 224760 KB Output is correct
20 Correct 290 ms 224632 KB Output is correct
21 Correct 310 ms 224624 KB Output is correct
22 Correct 244 ms 224580 KB Output is correct
23 Correct 308 ms 224460 KB Output is correct
24 Correct 449 ms 224580 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 312 ms 225452 KB Output is correct
3 Correct 282 ms 225532 KB Output is correct
4 Correct 235 ms 224876 KB Output is correct
5 Correct 245 ms 224824 KB Output is correct
6 Correct 300 ms 225080 KB Output is correct
7 Correct 290 ms 225068 KB Output is correct
8 Correct 240 ms 224844 KB Output is correct
9 Correct 185 ms 224824 KB Output is correct
10 Correct 262 ms 224592 KB Output is correct
11 Correct 327 ms 225064 KB Output is correct
12 Correct 524 ms 225088 KB Output is correct
13 Correct 320 ms 205384 KB Output is correct
14 Correct 4 ms 4932 KB Output is correct
15 Correct 269 ms 225208 KB Output is correct
16 Correct 297 ms 225192 KB Output is correct
17 Correct 337 ms 224716 KB Output is correct
18 Correct 279 ms 224424 KB Output is correct
19 Correct 295 ms 224760 KB Output is correct
20 Correct 290 ms 224632 KB Output is correct
21 Correct 310 ms 224624 KB Output is correct
22 Correct 244 ms 224580 KB Output is correct
23 Correct 308 ms 224460 KB Output is correct
24 Correct 449 ms 224580 KB Output is correct
25 Correct 242 ms 223788 KB Output is correct
26 Correct 288 ms 224588 KB Output is correct
27 Correct 272 ms 224460 KB Output is correct
28 Correct 272 ms 224408 KB Output is correct
29 Correct 306 ms 224452 KB Output is correct
30 Correct 335 ms 224460 KB Output is correct
31 Correct 375 ms 224296 KB Output is correct
32 Correct 470 ms 224324 KB Output is correct
33 Correct 500 ms 224116 KB Output is correct
34 Correct 916 ms 224104 KB Output is correct
35 Correct 434 ms 224188 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4932 KB Output is correct
2 Correct 2851 ms 1783680 KB Output is correct
3 Correct 2735 ms 1784104 KB Output is correct
4 Correct 2683 ms 1783968 KB Output is correct
5 Correct 2367 ms 1783840 KB Output is correct
6 Correct 2899 ms 1783812 KB Output is correct
7 Correct 2605 ms 1783764 KB Output is correct
8 Correct 4 ms 4948 KB Output is correct
9 Correct 312 ms 225452 KB Output is correct
10 Correct 282 ms 225532 KB Output is correct
11 Correct 235 ms 224876 KB Output is correct
12 Correct 245 ms 224824 KB Output is correct
13 Correct 300 ms 225080 KB Output is correct
14 Correct 290 ms 225068 KB Output is correct
15 Correct 240 ms 224844 KB Output is correct
16 Correct 185 ms 224824 KB Output is correct
17 Correct 262 ms 224592 KB Output is correct
18 Correct 327 ms 225064 KB Output is correct
19 Correct 524 ms 225088 KB Output is correct
20 Correct 320 ms 205384 KB Output is correct
21 Correct 4 ms 4932 KB Output is correct
22 Correct 269 ms 225208 KB Output is correct
23 Correct 297 ms 225192 KB Output is correct
24 Correct 337 ms 224716 KB Output is correct
25 Correct 279 ms 224424 KB Output is correct
26 Correct 295 ms 224760 KB Output is correct
27 Correct 290 ms 224632 KB Output is correct
28 Correct 310 ms 224624 KB Output is correct
29 Correct 244 ms 224580 KB Output is correct
30 Correct 308 ms 224460 KB Output is correct
31 Correct 449 ms 224580 KB Output is correct
32 Correct 242 ms 223788 KB Output is correct
33 Correct 288 ms 224588 KB Output is correct
34 Correct 272 ms 224460 KB Output is correct
35 Correct 272 ms 224408 KB Output is correct
36 Correct 306 ms 224452 KB Output is correct
37 Correct 335 ms 224460 KB Output is correct
38 Correct 375 ms 224296 KB Output is correct
39 Correct 470 ms 224324 KB Output is correct
40 Correct 500 ms 224116 KB Output is correct
41 Correct 916 ms 224104 KB Output is correct
42 Correct 434 ms 224188 KB Output is correct
43 Correct 1 ms 468 KB Output is correct
44 Correct 5 ms 4948 KB Output is correct
45 Correct 3060 ms 1781408 KB Output is correct
46 Correct 2603 ms 1781820 KB Output is correct
47 Correct 2554 ms 1781876 KB Output is correct
48 Correct 2706 ms 1781792 KB Output is correct
49 Correct 3705 ms 1781924 KB Output is correct
50 Correct 2913 ms 1782172 KB Output is correct
51 Correct 2694 ms 1782148 KB Output is correct
52 Correct 2878 ms 1782180 KB Output is correct
53 Correct 4157 ms 1782180 KB Output is correct
54 Correct 3517 ms 1790320 KB Output is correct
55 Correct 4008 ms 1789340 KB Output is correct
56 Correct 3512 ms 1789988 KB Output is correct
57 Correct 4022 ms 1790176 KB Output is correct
58 Correct 3982 ms 1790124 KB Output is correct
59 Correct 4014 ms 1790240 KB Output is correct
60 Correct 4635 ms 1789472 KB Output is correct
61 Correct 4155 ms 1789476 KB Output is correct