oj.uz

Submission #775293

# Submission time Handle Problem Language Result Execution time Memory
775293 2023-07-06T09:28:48 Z SanguineChameleon Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3898 ms 1302760 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 4e5 + 20;
const int maxT = 9;
const int maxK = 30;
const int inf = 1e9 + 20;
pair<int, pair<int, int>> jump[maxT][maxN][maxK];
long long rem[maxN];
int S[maxN];
int P[maxN];
int W[maxN];
int L[maxN];
vector<int> times;
int N, T;

void init(int _N, vector<int> _S, vector<int> _P, vector<int> _W, vector<int> _L) {
	N = _N;
	for (int i = 0; i < N; i++) {
		S[i] = _S[i];
		P[i] = _P[i];
		W[i] = _W[i];
		L[i] = _L[i];
	}
	W[N] = N;
	for (int i = 0; i < maxT; i++) {
		times.push_back(1 << (i * 3));
	}
	sort(times.begin(), times.end());
	T = times.size();
	for (int t = 0; t < T; t++) {
		for (int i = 0; i < N; i++) {
			if (t > 0 && S[i] <= times[t - 1]) {
				jump[t][i][0].first = W[i];
				jump[t][i][0].second.first = S[i];
				jump[t][i][0].second.second = -inf;
			}
			else {
				jump[t][i][0].first = L[i];
				jump[t][i][0].second.first = P[i];
				jump[t][i][0].second.second = -S[i];
			}
		}
		jump[t][N][0].first = N;
		jump[t][N][0].second.first = 0;
		jump[t][N][0].second.second = -inf;
		for (int k = 1; k < maxK; k++) {
			jump[t][N][k].first = N;
			jump[t][N][k].second.first = 0;
			jump[t][N][k].second.second = -inf;
			for (int i = 0; i < N; i++) {
				int nxt = jump[t][i][k - 1].first;
				jump[t][i][k].first = jump[t][nxt][k - 1].first;
				jump[t][i][k].second.first = min(inf, jump[t][i][k - 1].second.first + jump[t][nxt][k - 1].second.first);
				jump[t][i][k].second.second = max(jump[t][i][k - 1].second.second, jump[t][i][k - 1].second.first + jump[t][nxt][k - 1].second.second);
			}
		}
	}
	for (int i = N - 1; i >= 0; i--) {
		rem[i] = rem[W[i]] + S[i];
	}
	return;
}

long long simulate(int X, int _Z) {
	long long Z = _Z;
	int t = 0;
	while (X != N) {
		while (t < T && times[t] <= Z) {
			t++;
		}
		if (t == T) {
			break;
		}
		int sum = 0;
		for (int k = maxK - 1; k >= 0; k--) {
			if (sum + jump[t][X][k].second.first < inf && Z + jump[t][X][k].second.second < 0) {
				Z += jump[t][X][k].second.first;
				sum += jump[t][X][k].second.first;
				X = jump[t][X][k].first;
			}
		}
		if (Z >= S[X]) {
			Z += S[X];
			X = W[X];
		}
		else {
			Z += P[X];
			X = L[X];
		}
	}
	return Z + rem[X];
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 6 ms 6868 KB Output is correct
4 Correct 151 ms 161600 KB Output is correct
5 Correct 5 ms 6860 KB Output is correct
6 Correct 151 ms 161560 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3660 KB Output is correct
2 Correct 2778 ms 1291088 KB Output is correct
3 Correct 2311 ms 1297904 KB Output is correct
4 Correct 2360 ms 1299512 KB Output is correct
5 Correct 2375 ms 1299536 KB Output is correct
6 Correct 2428 ms 1298024 KB Output is correct
7 Correct 2245 ms 1296240 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3668 KB Output is correct
2 Correct 198 ms 164040 KB Output is correct
3 Correct 201 ms 164148 KB Output is correct
4 Correct 170 ms 163528 KB Output is correct
5 Correct 169 ms 163452 KB Output is correct
6 Correct 203 ms 163656 KB Output is correct
7 Correct 213 ms 163644 KB Output is correct
8 Correct 181 ms 163392 KB Output is correct
9 Correct 180 ms 163400 KB Output is correct
10 Correct 180 ms 163260 KB Output is correct
11 Correct 216 ms 163644 KB Output is correct
12 Correct 320 ms 163764 KB Output is correct
13 Correct 241 ms 163664 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3668 KB Output is correct
2 Correct 198 ms 164040 KB Output is correct
3 Correct 201 ms 164148 KB Output is correct
4 Correct 170 ms 163528 KB Output is correct
5 Correct 169 ms 163452 KB Output is correct
6 Correct 203 ms 163656 KB Output is correct
7 Correct 213 ms 163644 KB Output is correct
8 Correct 181 ms 163392 KB Output is correct
9 Correct 180 ms 163400 KB Output is correct
10 Correct 180 ms 163260 KB Output is correct
11 Correct 216 ms 163644 KB Output is correct
12 Correct 320 ms 163764 KB Output is correct
13 Correct 241 ms 163664 KB Output is correct
14 Correct 3 ms 3668 KB Output is correct
15 Correct 213 ms 163844 KB Output is correct
16 Correct 195 ms 164060 KB Output is correct
17 Correct 185 ms 163544 KB Output is correct
18 Correct 199 ms 163588 KB Output is correct
19 Correct 213 ms 163660 KB Output is correct
20 Correct 241 ms 163416 KB Output is correct
21 Correct 223 ms 163468 KB Output is correct
22 Correct 215 ms 163568 KB Output is correct
23 Correct 280 ms 163600 KB Output is correct
24 Correct 287 ms 163640 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3668 KB Output is correct
2 Correct 198 ms 164040 KB Output is correct
3 Correct 201 ms 164148 KB Output is correct
4 Correct 170 ms 163528 KB Output is correct
5 Correct 169 ms 163452 KB Output is correct
6 Correct 203 ms 163656 KB Output is correct
7 Correct 213 ms 163644 KB Output is correct
8 Correct 181 ms 163392 KB Output is correct
9 Correct 180 ms 163400 KB Output is correct
10 Correct 180 ms 163260 KB Output is correct
11 Correct 216 ms 163644 KB Output is correct
12 Correct 320 ms 163764 KB Output is correct
13 Correct 241 ms 163664 KB Output is correct
14 Correct 3 ms 3668 KB Output is correct
15 Correct 213 ms 163844 KB Output is correct
16 Correct 195 ms 164060 KB Output is correct
17 Correct 185 ms 163544 KB Output is correct
18 Correct 199 ms 163588 KB Output is correct
19 Correct 213 ms 163660 KB Output is correct
20 Correct 241 ms 163416 KB Output is correct
21 Correct 223 ms 163468 KB Output is correct
22 Correct 215 ms 163568 KB Output is correct
23 Correct 280 ms 163600 KB Output is correct
24 Correct 287 ms 163640 KB Output is correct
25 Correct 238 ms 162976 KB Output is correct
26 Correct 196 ms 164016 KB Output is correct
27 Correct 182 ms 163472 KB Output is correct
28 Correct 218 ms 163544 KB Output is correct
29 Correct 240 ms 163940 KB Output is correct
30 Correct 215 ms 163688 KB Output is correct
31 Correct 226 ms 163428 KB Output is correct
32 Correct 327 ms 163556 KB Output is correct
33 Correct 410 ms 163580 KB Output is correct
34 Correct 737 ms 163484 KB Output is correct
35 Correct 323 ms 163552 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3660 KB Output is correct
2 Correct 2778 ms 1291088 KB Output is correct
3 Correct 2311 ms 1297904 KB Output is correct
4 Correct 2360 ms 1299512 KB Output is correct
5 Correct 2375 ms 1299536 KB Output is correct
6 Correct 2428 ms 1298024 KB Output is correct
7 Correct 2245 ms 1296240 KB Output is correct
8 Correct 3 ms 3668 KB Output is correct
9 Correct 198 ms 164040 KB Output is correct
10 Correct 201 ms 164148 KB Output is correct
11 Correct 170 ms 163528 KB Output is correct
12 Correct 169 ms 163452 KB Output is correct
13 Correct 203 ms 163656 KB Output is correct
14 Correct 213 ms 163644 KB Output is correct
15 Correct 181 ms 163392 KB Output is correct
16 Correct 180 ms 163400 KB Output is correct
17 Correct 180 ms 163260 KB Output is correct
18 Correct 216 ms 163644 KB Output is correct
19 Correct 320 ms 163764 KB Output is correct
20 Correct 241 ms 163664 KB Output is correct
21 Correct 3 ms 3668 KB Output is correct
22 Correct 213 ms 163844 KB Output is correct
23 Correct 195 ms 164060 KB Output is correct
24 Correct 185 ms 163544 KB Output is correct
25 Correct 199 ms 163588 KB Output is correct
26 Correct 213 ms 163660 KB Output is correct
27 Correct 241 ms 163416 KB Output is correct
28 Correct 223 ms 163468 KB Output is correct
29 Correct 215 ms 163568 KB Output is correct
30 Correct 280 ms 163600 KB Output is correct
31 Correct 287 ms 163640 KB Output is correct
32 Correct 238 ms 162976 KB Output is correct
33 Correct 196 ms 164016 KB Output is correct
34 Correct 182 ms 163472 KB Output is correct
35 Correct 218 ms 163544 KB Output is correct
36 Correct 240 ms 163940 KB Output is correct
37 Correct 215 ms 163688 KB Output is correct
38 Correct 226 ms 163428 KB Output is correct
39 Correct 327 ms 163556 KB Output is correct
40 Correct 410 ms 163580 KB Output is correct
41 Correct 737 ms 163484 KB Output is correct
42 Correct 323 ms 163552 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 3 ms 3668 KB Output is correct
45 Correct 2498 ms 1302760 KB Output is correct
46 Correct 2660 ms 1298048 KB Output is correct
47 Correct 2305 ms 1298432 KB Output is correct
48 Correct 2361 ms 1300612 KB Output is correct
49 Correct 2590 ms 1302696 KB Output is correct
50 Correct 2638 ms 1300332 KB Output is correct
51 Correct 2452 ms 1300600 KB Output is correct
52 Correct 2399 ms 1298288 KB Output is correct
53 Correct 3305 ms 1299092 KB Output is correct
54 Correct 2927 ms 1300192 KB Output is correct
55 Correct 3674 ms 1299252 KB Output is correct
56 Correct 2961 ms 1299888 KB Output is correct
57 Correct 3296 ms 1300008 KB Output is correct
58 Correct 2950 ms 1300000 KB Output is correct
59 Correct 3049 ms 1300188 KB Output is correct
60 Correct 3898 ms 1299440 KB Output is correct
61 Correct 3519 ms 1299388 KB Output is correct