oj.uz

Submission #775297

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

const int maxN = 4e5 + 20;
const int maxT = 9;
const int maxK = 25;
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 1 ms 304 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 4 ms 5828 KB Output is correct
4 Correct 185 ms 136248 KB Output is correct
5 Correct 4 ms 5828 KB Output is correct
6 Correct 135 ms 136140 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 1873 ms 1086588 KB Output is correct
3 Correct 1757 ms 1086664 KB Output is correct
4 Correct 2036 ms 1088280 KB Output is correct
5 Correct 1779 ms 1088300 KB Output is correct
6 Correct 1945 ms 1086648 KB Output is correct
7 Correct 1752 ms 1085000 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3156 KB Output is correct
2 Correct 178 ms 137632 KB Output is correct
3 Correct 154 ms 137764 KB Output is correct
4 Correct 145 ms 137164 KB Output is correct
5 Correct 143 ms 137024 KB Output is correct
6 Correct 180 ms 137344 KB Output is correct
7 Correct 168 ms 137292 KB Output is correct
8 Correct 163 ms 137036 KB Output is correct
9 Correct 168 ms 137000 KB Output is correct
10 Correct 153 ms 136848 KB Output is correct
11 Correct 206 ms 137260 KB Output is correct
12 Correct 280 ms 137284 KB Output is correct
13 Correct 199 ms 137192 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3156 KB Output is correct
2 Correct 178 ms 137632 KB Output is correct
3 Correct 154 ms 137764 KB Output is correct
4 Correct 145 ms 137164 KB Output is correct
5 Correct 143 ms 137024 KB Output is correct
6 Correct 180 ms 137344 KB Output is correct
7 Correct 168 ms 137292 KB Output is correct
8 Correct 163 ms 137036 KB Output is correct
9 Correct 168 ms 137000 KB Output is correct
10 Correct 153 ms 136848 KB Output is correct
11 Correct 206 ms 137260 KB Output is correct
12 Correct 280 ms 137284 KB Output is correct
13 Correct 199 ms 137192 KB Output is correct
14 Correct 3 ms 3060 KB Output is correct
15 Correct 166 ms 137472 KB Output is correct
16 Correct 216 ms 137528 KB Output is correct
17 Correct 149 ms 137144 KB Output is correct
18 Correct 157 ms 137232 KB Output is correct
19 Correct 180 ms 137340 KB Output is correct
20 Correct 169 ms 137036 KB Output is correct
21 Correct 176 ms 137104 KB Output is correct
22 Correct 198 ms 137092 KB Output is correct
23 Correct 185 ms 137292 KB Output is correct
24 Correct 289 ms 137288 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3156 KB Output is correct
2 Correct 178 ms 137632 KB Output is correct
3 Correct 154 ms 137764 KB Output is correct
4 Correct 145 ms 137164 KB Output is correct
5 Correct 143 ms 137024 KB Output is correct
6 Correct 180 ms 137344 KB Output is correct
7 Correct 168 ms 137292 KB Output is correct
8 Correct 163 ms 137036 KB Output is correct
9 Correct 168 ms 137000 KB Output is correct
10 Correct 153 ms 136848 KB Output is correct
11 Correct 206 ms 137260 KB Output is correct
12 Correct 280 ms 137284 KB Output is correct
13 Correct 199 ms 137192 KB Output is correct
14 Correct 3 ms 3060 KB Output is correct
15 Correct 166 ms 137472 KB Output is correct
16 Correct 216 ms 137528 KB Output is correct
17 Correct 149 ms 137144 KB Output is correct
18 Correct 157 ms 137232 KB Output is correct
19 Correct 180 ms 137340 KB Output is correct
20 Correct 169 ms 137036 KB Output is correct
21 Correct 176 ms 137104 KB Output is correct
22 Correct 198 ms 137092 KB Output is correct
23 Correct 185 ms 137292 KB Output is correct
24 Correct 289 ms 137288 KB Output is correct
25 Correct 149 ms 136516 KB Output is correct
26 Correct 170 ms 137552 KB Output is correct
27 Correct 154 ms 137032 KB Output is correct
28 Correct 163 ms 137288 KB Output is correct
29 Correct 187 ms 137544 KB Output is correct
30 Correct 186 ms 137228 KB Output is correct
31 Correct 242 ms 136972 KB Output is correct
32 Correct 264 ms 137156 KB Output is correct
33 Correct 331 ms 137212 KB Output is correct
34 Correct 737 ms 137064 KB Output is correct
35 Correct 283 ms 137136 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 1873 ms 1086588 KB Output is correct
3 Correct 1757 ms 1086664 KB Output is correct
4 Correct 2036 ms 1088280 KB Output is correct
5 Correct 1779 ms 1088300 KB Output is correct
6 Correct 1945 ms 1086648 KB Output is correct
7 Correct 1752 ms 1085000 KB Output is correct
8 Correct 3 ms 3156 KB Output is correct
9 Correct 178 ms 137632 KB Output is correct
10 Correct 154 ms 137764 KB Output is correct
11 Correct 145 ms 137164 KB Output is correct
12 Correct 143 ms 137024 KB Output is correct
13 Correct 180 ms 137344 KB Output is correct
14 Correct 168 ms 137292 KB Output is correct
15 Correct 163 ms 137036 KB Output is correct
16 Correct 168 ms 137000 KB Output is correct
17 Correct 153 ms 136848 KB Output is correct
18 Correct 206 ms 137260 KB Output is correct
19 Correct 280 ms 137284 KB Output is correct
20 Correct 199 ms 137192 KB Output is correct
21 Correct 3 ms 3060 KB Output is correct
22 Correct 166 ms 137472 KB Output is correct
23 Correct 216 ms 137528 KB Output is correct
24 Correct 149 ms 137144 KB Output is correct
25 Correct 157 ms 137232 KB Output is correct
26 Correct 180 ms 137340 KB Output is correct
27 Correct 169 ms 137036 KB Output is correct
28 Correct 176 ms 137104 KB Output is correct
29 Correct 198 ms 137092 KB Output is correct
30 Correct 185 ms 137292 KB Output is correct
31 Correct 289 ms 137288 KB Output is correct
32 Correct 149 ms 136516 KB Output is correct
33 Correct 170 ms 137552 KB Output is correct
34 Correct 154 ms 137032 KB Output is correct
35 Correct 163 ms 137288 KB Output is correct
36 Correct 187 ms 137544 KB Output is correct
37 Correct 186 ms 137228 KB Output is correct
38 Correct 242 ms 136972 KB Output is correct
39 Correct 264 ms 137156 KB Output is correct
40 Correct 331 ms 137212 KB Output is correct
41 Correct 737 ms 137064 KB Output is correct
42 Correct 283 ms 137136 KB Output is correct
43 Correct 1 ms 312 KB Output is correct
44 Correct 3 ms 3156 KB Output is correct
45 Correct 2004 ms 1091368 KB Output is correct
46 Correct 1827 ms 1086764 KB Output is correct
47 Correct 1833 ms 1087116 KB Output is correct
48 Correct 1871 ms 1089324 KB Output is correct
49 Correct 1927 ms 1091372 KB Output is correct
50 Correct 1999 ms 1089032 KB Output is correct
51 Correct 1800 ms 1089320 KB Output is correct
52 Correct 2161 ms 1087052 KB Output is correct
53 Correct 3009 ms 1087812 KB Output is correct
54 Correct 2464 ms 1088800 KB Output is correct
55 Correct 3198 ms 1087620 KB Output is correct
56 Correct 2488 ms 1086420 KB Output is correct
57 Correct 2757 ms 1085220 KB Output is correct
58 Correct 2621 ms 1083920 KB Output is correct
59 Correct 2602 ms 1082304 KB Output is correct
60 Correct 3355 ms 1080932 KB Output is correct
61 Correct 3088 ms 1079748 KB Output is correct