oj.uz

Submission #993353

# Submission time Handle Problem Language Result Execution time Memory
993353 2024-06-05T13:59:49 Z pavement Dungeons Game (IOI21_dungeons) C++17
100 / 100
 4027 ms 1387344 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define pb push_back

const int MAX_N = 400000, BAND_LIM = 24, DECOMP_LIM = 12;
int n, to[BAND_LIM][DECOMP_LIM][MAX_N + 1], wei[BAND_LIM][DECOMP_LIM][MAX_N + 1], lim[BAND_LIM][DECOMP_LIM][MAX_N + 1], s[MAX_N + 1], p[MAX_N + 1], w[MAX_N + 1], l[MAX_N + 1];
ll winner[MAX_N + 1];

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
	::n = n;
	copy(s.begin(), s.end(), ::s);
	copy(p.begin(), p.end(), ::p);
	copy(w.begin(), w.end(), ::w);
	copy(l.begin(), l.end(), ::l);
	::w[n] = n;
	::l[n] = n;
	for (int i = n - 1; i >= 0; i--) {
		winner[i] = winner[w[i]] + s[i];
	}
	for (int b = 0; b < BAND_LIM; b++) {
		int lb = (1 << b), rb = (1 << (b + 1)) - 1;
		for (int i = 0; i <= n; i++) {
			if (s[i] < lb) { // instant-win
				to[b][0][i] = ::w[i];
				wei[b][0][i] = s[i];
				lim[b][0][i] = INT_MAX;
			} else if (s[i] > rb) { // instant-lose
				to[b][0][i] = ::l[i];
				wei[b][0][i] = p[i];
				lim[b][0][i] = INT_MAX;
			} else {
				to[b][0][i] = ::l[i];
				wei[b][0][i] = p[i];
				lim[b][0][i] = s[i];
			}
		}
		assert(to[b][0][n] == n);
		for (int k = 1; k < DECOMP_LIM; k++) {
			for (int i = 0; i <= n; i++) {
				to[b][k][i] = to[b][k - 1][i];
				wei[b][k][i] = wei[b][k - 1][i];
				lim[b][k][i] = lim[b][k - 1][i];
				for (int rep = 0; rep < 3; rep++) {
					lim[b][k][i] = max(0, min(lim[b][k][i], lim[b][k - 1][to[b][k][i]] - wei[b][k][i]));
					wei[b][k][i] = min(rb, wei[b][k][i] + wei[b][k - 1][to[b][k][i]]);
					to[b][k][i] = to[b][k - 1][to[b][k][i]];
				}
				if (i == n) {
					assert(to[b][k][i] == n);
				}
			}
		}
	}
}

ll simulate(int x, int _z) {
	ll z = _z;
	for (int b = 0; b < BAND_LIM; b++) {
		int rb = (1 << (b + 1)) - 1;
		if (z > rb) { // past this band
			continue;
		}
		for (int k = DECOMP_LIM - 1; k >= 0; k--) {
			for (int rep = 0; rep < 3; rep++) {
				if (lim[b][k][x] <= z || wei[b][k][x] > rb - z) {
					continue;
				}
				z += wei[b][k][x];
				x = to[b][k][x];
			}
		}
		if (x == n) {
			return z;
		}
		for (int iter = 0; iter < 2; iter++) {
			if (z >= s[x]) {
				z += s[x];
				x = w[x];
			} else {
				z += p[x];
				x = l[x];
			}
			if (x == n) {
				return z;
			}
		}
		assert(z > rb);
	}
	// win all the way
	return z + winner[x];
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 9 ms 13404 KB Output is correct
4 Correct 210 ms 179056 KB Output is correct
5 Correct 10 ms 13404 KB Output is correct
6 Correct 191 ms 178824 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9820 KB Output is correct
2 Correct 1606 ms 1379772 KB Output is correct
3 Correct 1579 ms 1382460 KB Output is correct
4 Correct 1729 ms 1384016 KB Output is correct
5 Correct 1687 ms 1384020 KB Output is correct
6 Correct 2686 ms 1382604 KB Output is correct
7 Correct 2518 ms 1380676 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 24252 KB Output is correct
2 Correct 330 ms 192848 KB Output is correct
3 Correct 281 ms 185816 KB Output is correct
4 Correct 201 ms 188756 KB Output is correct
5 Correct 229 ms 188736 KB Output is correct
6 Correct 573 ms 190824 KB Output is correct
7 Correct 564 ms 189000 KB Output is correct
8 Correct 540 ms 192336 KB Output is correct
9 Correct 242 ms 185200 KB Output is correct
10 Correct 504 ms 184912 KB Output is correct
11 Correct 753 ms 192476 KB Output is correct
12 Correct 2461 ms 192604 KB Output is correct
13 Correct 2188 ms 185320 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 24252 KB Output is correct
2 Correct 330 ms 192848 KB Output is correct
3 Correct 281 ms 185816 KB Output is correct
4 Correct 201 ms 188756 KB Output is correct
5 Correct 229 ms 188736 KB Output is correct
6 Correct 573 ms 190824 KB Output is correct
7 Correct 564 ms 189000 KB Output is correct
8 Correct 540 ms 192336 KB Output is correct
9 Correct 242 ms 185200 KB Output is correct
10 Correct 504 ms 184912 KB Output is correct
11 Correct 753 ms 192476 KB Output is correct
12 Correct 2461 ms 192604 KB Output is correct
13 Correct 2188 ms 185320 KB Output is correct
14 Correct 8 ms 20060 KB Output is correct
15 Correct 275 ms 189012 KB Output is correct
16 Correct 334 ms 191128 KB Output is correct
17 Correct 260 ms 185304 KB Output is correct
18 Correct 334 ms 185308 KB Output is correct
19 Correct 551 ms 187024 KB Output is correct
20 Correct 514 ms 192132 KB Output is correct
21 Correct 559 ms 192348 KB Output is correct
22 Correct 678 ms 192336 KB Output is correct
23 Correct 1235 ms 192592 KB Output is correct
24 Correct 1125 ms 192596 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 24252 KB Output is correct
2 Correct 330 ms 192848 KB Output is correct
3 Correct 281 ms 185816 KB Output is correct
4 Correct 201 ms 188756 KB Output is correct
5 Correct 229 ms 188736 KB Output is correct
6 Correct 573 ms 190824 KB Output is correct
7 Correct 564 ms 189000 KB Output is correct
8 Correct 540 ms 192336 KB Output is correct
9 Correct 242 ms 185200 KB Output is correct
10 Correct 504 ms 184912 KB Output is correct
11 Correct 753 ms 192476 KB Output is correct
12 Correct 2461 ms 192604 KB Output is correct
13 Correct 2188 ms 185320 KB Output is correct
14 Correct 8 ms 20060 KB Output is correct
15 Correct 275 ms 189012 KB Output is correct
16 Correct 334 ms 191128 KB Output is correct
17 Correct 260 ms 185304 KB Output is correct
18 Correct 334 ms 185308 KB Output is correct
19 Correct 551 ms 187024 KB Output is correct
20 Correct 514 ms 192132 KB Output is correct
21 Correct 559 ms 192348 KB Output is correct
22 Correct 678 ms 192336 KB Output is correct
23 Correct 1235 ms 192592 KB Output is correct
24 Correct 1125 ms 192596 KB Output is correct
25 Correct 275 ms 191828 KB Output is correct
26 Correct 284 ms 192952 KB Output is correct
27 Correct 244 ms 192596 KB Output is correct
28 Correct 220 ms 192336 KB Output is correct
29 Correct 305 ms 192852 KB Output is correct
30 Correct 470 ms 192592 KB Output is correct
31 Correct 623 ms 192340 KB Output is correct
32 Correct 758 ms 192492 KB Output is correct
33 Correct 446 ms 192344 KB Output is correct
34 Correct 1022 ms 192340 KB Output is correct
35 Correct 882 ms 192476 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9820 KB Output is correct
2 Correct 1606 ms 1379772 KB Output is correct
3 Correct 1579 ms 1382460 KB Output is correct
4 Correct 1729 ms 1384016 KB Output is correct
5 Correct 1687 ms 1384020 KB Output is correct
6 Correct 2686 ms 1382604 KB Output is correct
7 Correct 2518 ms 1380676 KB Output is correct
8 Correct 7 ms 24252 KB Output is correct
9 Correct 330 ms 192848 KB Output is correct
10 Correct 281 ms 185816 KB Output is correct
11 Correct 201 ms 188756 KB Output is correct
12 Correct 229 ms 188736 KB Output is correct
13 Correct 573 ms 190824 KB Output is correct
14 Correct 564 ms 189000 KB Output is correct
15 Correct 540 ms 192336 KB Output is correct
16 Correct 242 ms 185200 KB Output is correct
17 Correct 504 ms 184912 KB Output is correct
18 Correct 753 ms 192476 KB Output is correct
19 Correct 2461 ms 192604 KB Output is correct
20 Correct 2188 ms 185320 KB Output is correct
21 Correct 8 ms 20060 KB Output is correct
22 Correct 275 ms 189012 KB Output is correct
23 Correct 334 ms 191128 KB Output is correct
24 Correct 260 ms 185304 KB Output is correct
25 Correct 334 ms 185308 KB Output is correct
26 Correct 551 ms 187024 KB Output is correct
27 Correct 514 ms 192132 KB Output is correct
28 Correct 559 ms 192348 KB Output is correct
29 Correct 678 ms 192336 KB Output is correct
30 Correct 1235 ms 192592 KB Output is correct
31 Correct 1125 ms 192596 KB Output is correct
32 Correct 275 ms 191828 KB Output is correct
33 Correct 284 ms 192952 KB Output is correct
34 Correct 244 ms 192596 KB Output is correct
35 Correct 220 ms 192336 KB Output is correct
36 Correct 305 ms 192852 KB Output is correct
37 Correct 470 ms 192592 KB Output is correct
38 Correct 623 ms 192340 KB Output is correct
39 Correct 758 ms 192492 KB Output is correct
40 Correct 446 ms 192344 KB Output is correct
41 Correct 1022 ms 192340 KB Output is correct
42 Correct 882 ms 192476 KB Output is correct
43 Correct 4 ms 20828 KB Output is correct
44 Correct 7 ms 24276 KB Output is correct
45 Correct 2693 ms 1387200 KB Output is correct
46 Correct 1773 ms 1382740 KB Output is correct
47 Correct 1674 ms 1383092 KB Output is correct
48 Correct 1523 ms 1385284 KB Output is correct
49 Correct 2712 ms 1387344 KB Output is correct
50 Correct 2060 ms 1384892 KB Output is correct
51 Correct 1542 ms 1385284 KB Output is correct
52 Correct 2244 ms 1382880 KB Output is correct
53 Correct 4027 ms 1383816 KB Output is correct
54 Correct 1888 ms 1384784 KB Output is correct
55 Correct 2573 ms 1383844 KB Output is correct
56 Correct 3551 ms 1384408 KB Output is correct
57 Correct 3533 ms 1384532 KB Output is correct
58 Correct 3390 ms 1384532 KB Output is correct
59 Correct 3367 ms 1384632 KB Output is correct
60 Correct 3594 ms 1383976 KB Output is correct
61 Correct 2546 ms 1384056 KB Output is correct