oj.uz

Submission #566460

# Submission time Handle Problem Language Result Execution time Memory
566460 2022-05-22T10:32:08 Z kartel Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3062 ms 714088 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 4 * (int)1e5;
const int C0 = 8;
const int C1 = 1;
const int H = 24;
const ll INF = 1e9 + 7;

pair<int, pair<ll, ll>> jmp[N + 1][H / C0][H / C1];
ll add[N + 1];
ll str[N + 1];
ll bns[N + 1];
int wt[N + 1];
int lt[N + 1];
int n;

pair<int, ll> advance(pair<int, ll> cur) {
	if (str[cur.first] > cur.second) return {lt[cur.first], bns[cur.first] + cur.second};
	else return {wt[cur.first], str[cur.first] + cur.second};
}

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) str[i] = s[i];
	for (int i = 0; i < n; ++i) bns[i] = p[i];
	for (int i = 0; i < n; ++i) wt[i] = w[i];
	for (int i = 0; i < n; ++i) lt[i] = l[i];
	str[n] = INF;
	bns[n] = INF;
	wt[n] = n;
	lt[n] = n;

	add[n] = 0;
	for (int i = n-1; i >= 0; --i) add[i] = add[wt[i]] + str[i];
	
	for (int a = 0; a < H / C0; ++a) {
		ll lo = 1 << (C0 * a);
		ll hi = 1 << (C0 * (a + 1));
		for (int i = 0; i <= n; ++i) {
			if ((lo < str[i] && str[i] < hi) || i == n) {
				jmp[i][a][0] = {lt[i], {str[i], bns[i]}};
			} else if (str[i] <= lo) {
				jmp[i][a][0] = {wt[i], {INF, str[i]}};
			} else {
				jmp[i][a][0] = {lt[i], {INF, bns[i]}};
			}
		}
		for (int b = 1; b < H / C1; ++b) {
			for (int i = 0; i <= n; ++i) {
				int j = i;
				ll min_str = INF, str_add = 0;
				for (int it = 0; it < (1 << C1); ++it) {
					auto pr = jmp[j][a][b - 1];
					min_str = min(min_str, pr.second.first - str_add);
					str_add += pr.second.second;
					j = pr.first;
				}
				jmp[i][a][b] = {j, {min_str, str_add}};
			}
		}
	}
}

long long simulate(int start_i, int ini_pwr) {
	pair<int, ll> state = {start_i, (ll)ini_pwr};
	for (int a = 0; a < H; ++a) {
		ll lo = 1 << (C0 * a);
		ll hi = 1 << (C0 * (a + 1));
		while(state.first != n && lo <= state.second && state.second < hi) {
			for (int b = (H/C1) - 1; b >= 0; --b) {
				while(state.second < jmp[state.first][a][b].second.first && state.second + jmp[state.first][a][b].second.second < hi) {
					state.second += jmp[state.first][a][b].second.second;
					state.first = jmp[state.first][a][b].first;
				}
			}
			if (state.first != n) state = advance(state); // either win against opponent in same strength bracket, or break out of strength bracket
		}
	}
	return state.second + add[state.first];
}

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 4 ms 3856 KB Output is correct
4 Correct 118 ms 88068 KB Output is correct
5 Correct 5 ms 3796 KB Output is correct
6 Correct 116 ms 88080 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2120 KB Output is correct
2 Correct 1228 ms 702532 KB Output is correct
3 Correct 1127 ms 702456 KB Output is correct
4 Correct 1086 ms 702460 KB Output is correct
5 Correct 1074 ms 702456 KB Output is correct
6 Correct 1569 ms 709356 KB Output is correct
7 Correct 1890 ms 707564 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2004 KB Output is correct
2 Correct 167 ms 88800 KB Output is correct
3 Correct 172 ms 88796 KB Output is correct
4 Correct 142 ms 88732 KB Output is correct
5 Correct 150 ms 88800 KB Output is correct
6 Correct 161 ms 88796 KB Output is correct
7 Correct 149 ms 88800 KB Output is correct
8 Correct 242 ms 88788 KB Output is correct
9 Correct 143 ms 88800 KB Output is correct
10 Correct 441 ms 88732 KB Output is correct
11 Correct 179 ms 88672 KB Output is correct
12 Correct 323 ms 88804 KB Output is correct
13 Correct 341 ms 88784 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2004 KB Output is correct
2 Correct 167 ms 88800 KB Output is correct
3 Correct 172 ms 88796 KB Output is correct
4 Correct 142 ms 88732 KB Output is correct
5 Correct 150 ms 88800 KB Output is correct
6 Correct 161 ms 88796 KB Output is correct
7 Correct 149 ms 88800 KB Output is correct
8 Correct 242 ms 88788 KB Output is correct
9 Correct 143 ms 88800 KB Output is correct
10 Correct 441 ms 88732 KB Output is correct
11 Correct 179 ms 88672 KB Output is correct
12 Correct 323 ms 88804 KB Output is correct
13 Correct 341 ms 88784 KB Output is correct
14 Correct 2 ms 2004 KB Output is correct
15 Correct 159 ms 88808 KB Output is correct
16 Correct 162 ms 88780 KB Output is correct
17 Correct 159 ms 88804 KB Output is correct
18 Correct 192 ms 88780 KB Output is correct
19 Correct 193 ms 88716 KB Output is correct
20 Correct 336 ms 88808 KB Output is correct
21 Correct 611 ms 88804 KB Output is correct
22 Correct 794 ms 88772 KB Output is correct
23 Correct 223 ms 88708 KB Output is correct
24 Correct 397 ms 88796 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2004 KB Output is correct
2 Correct 167 ms 88800 KB Output is correct
3 Correct 172 ms 88796 KB Output is correct
4 Correct 142 ms 88732 KB Output is correct
5 Correct 150 ms 88800 KB Output is correct
6 Correct 161 ms 88796 KB Output is correct
7 Correct 149 ms 88800 KB Output is correct
8 Correct 242 ms 88788 KB Output is correct
9 Correct 143 ms 88800 KB Output is correct
10 Correct 441 ms 88732 KB Output is correct
11 Correct 179 ms 88672 KB Output is correct
12 Correct 323 ms 88804 KB Output is correct
13 Correct 341 ms 88784 KB Output is correct
14 Correct 2 ms 2004 KB Output is correct
15 Correct 159 ms 88808 KB Output is correct
16 Correct 162 ms 88780 KB Output is correct
17 Correct 159 ms 88804 KB Output is correct
18 Correct 192 ms 88780 KB Output is correct
19 Correct 193 ms 88716 KB Output is correct
20 Correct 336 ms 88808 KB Output is correct
21 Correct 611 ms 88804 KB Output is correct
22 Correct 794 ms 88772 KB Output is correct
23 Correct 223 ms 88708 KB Output is correct
24 Correct 397 ms 88796 KB Output is correct
25 Correct 101 ms 88152 KB Output is correct
26 Correct 140 ms 88680 KB Output is correct
27 Correct 145 ms 88792 KB Output is correct
28 Correct 158 ms 88692 KB Output is correct
29 Correct 155 ms 88696 KB Output is correct
30 Correct 259 ms 88748 KB Output is correct
31 Correct 345 ms 88692 KB Output is correct
32 Correct 346 ms 88780 KB Output is correct
33 Correct 588 ms 88884 KB Output is correct
34 Correct 892 ms 88652 KB Output is correct
35 Correct 1149 ms 88780 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2120 KB Output is correct
2 Correct 1228 ms 702532 KB Output is correct
3 Correct 1127 ms 702456 KB Output is correct
4 Correct 1086 ms 702460 KB Output is correct
5 Correct 1074 ms 702456 KB Output is correct
6 Correct 1569 ms 709356 KB Output is correct
7 Correct 1890 ms 707564 KB Output is correct
8 Correct 2 ms 2004 KB Output is correct
9 Correct 167 ms 88800 KB Output is correct
10 Correct 172 ms 88796 KB Output is correct
11 Correct 142 ms 88732 KB Output is correct
12 Correct 150 ms 88800 KB Output is correct
13 Correct 161 ms 88796 KB Output is correct
14 Correct 149 ms 88800 KB Output is correct
15 Correct 242 ms 88788 KB Output is correct
16 Correct 143 ms 88800 KB Output is correct
17 Correct 441 ms 88732 KB Output is correct
18 Correct 179 ms 88672 KB Output is correct
19 Correct 323 ms 88804 KB Output is correct
20 Correct 341 ms 88784 KB Output is correct
21 Correct 2 ms 2004 KB Output is correct
22 Correct 159 ms 88808 KB Output is correct
23 Correct 162 ms 88780 KB Output is correct
24 Correct 159 ms 88804 KB Output is correct
25 Correct 192 ms 88780 KB Output is correct
26 Correct 193 ms 88716 KB Output is correct
27 Correct 336 ms 88808 KB Output is correct
28 Correct 611 ms 88804 KB Output is correct
29 Correct 794 ms 88772 KB Output is correct
30 Correct 223 ms 88708 KB Output is correct
31 Correct 397 ms 88796 KB Output is correct
32 Correct 101 ms 88152 KB Output is correct
33 Correct 140 ms 88680 KB Output is correct
34 Correct 145 ms 88792 KB Output is correct
35 Correct 158 ms 88692 KB Output is correct
36 Correct 155 ms 88696 KB Output is correct
37 Correct 259 ms 88748 KB Output is correct
38 Correct 345 ms 88692 KB Output is correct
39 Correct 346 ms 88780 KB Output is correct
40 Correct 588 ms 88884 KB Output is correct
41 Correct 892 ms 88652 KB Output is correct
42 Correct 1149 ms 88780 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 2 ms 2116 KB Output is correct
45 Correct 1213 ms 714084 KB Output is correct
46 Correct 1043 ms 709460 KB Output is correct
47 Correct 1065 ms 709864 KB Output is correct
48 Correct 981 ms 712056 KB Output is correct
49 Correct 1147 ms 714088 KB Output is correct
50 Correct 1168 ms 711660 KB Output is correct
51 Correct 918 ms 712044 KB Output is correct
52 Correct 1159 ms 709744 KB Output is correct
53 Correct 1822 ms 710504 KB Output is correct
54 Correct 1616 ms 711716 KB Output is correct
55 Correct 2131 ms 710624 KB Output is correct
56 Correct 2941 ms 711312 KB Output is correct
57 Correct 2079 ms 711404 KB Output is correct
58 Correct 2158 ms 711400 KB Output is correct
59 Correct 1950 ms 711456 KB Output is correct
60 Correct 3062 ms 710760 KB Output is correct
61 Correct 2993 ms 710832 KB Output is correct