oj.uz

Submission #438653

# Submission time Handle Problem Language Result Execution time Memory
438653 2021-06-28T11:10:34 Z fleimgruber Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 738316 KB 
#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 400001;
const int MAX_LOG = 25; // 2^24 > 10^7

int n, s[MAX_N], p[MAX_N], w[MAX_N], l[MAX_N];

// MLE for other subtasks. probably requires smarter jump pointers
struct Subtask1345 {
	// dp[i][j][k] = we're at i, simulate for 2^j steps and
	// win against an opponent if strength < 2^k (we don't gain strength)
	struct {
		int end; // where do we end up at?
		long long gained; // total strength gained on the path
		// max(sum(gained) - opponent) along the simulation,
		// for all opponents we lose against
		long long max;
	} dp[50001][MAX_LOG][MAX_LOG];

	Subtask1345() {
		for (int j = 0; j < MAX_LOG; j++)
			for (int i = 0; i <= n; i++)
				for (int k = 0; k < MAX_LOG; k++) {
					auto& x = dp[i][j][k];
					if (j == 0)
						if (i == n) {
							x.end = n;
							x.gained = x.max = 0;
						} else if (s[i] < (1 << k)) { // we win
							x.end = w[i];
							x.gained = s[i];
							x.max = LLONG_MIN;
						} else {
							x.end = l[i];
							x.gained = p[i];
							// 1 step behind (we didn't gain 'gained' yet)
							x.max = -s[i];
						}
					else {
						auto& a = dp[i][j - 1][k];
						auto& b = dp[a.end][j - 1][k];
						x.end = b.end;
						x.gained = a.gained + b.gained;
						x.max = max(a.max, a.gained + b.max);
					}
				}
	}

	long long simulate(int at, long long strength) {
		int k = 0;
		auto advance_k = [&] { // msb
			if (strength >= (1 << 24))
				k = 24;
			else
				while ((1 << (k + 1)) <= strength)
					k++;
		};
		// find first time our dp takes the wrong turn. once this
		// happens, the msb will change => happens only log(something)
		// times at this vertex we win:
		//	strength + gained - opponent >= 0
		// => strength + dp.max >= 0
		// but dp loses (dp.max is only calculated for losing edges)
		auto wrong_turn = [&](int i, int j, int k) {
			return strength + dp[i][j][k].max >= 0;
		};
		while (at != n) {
			advance_k();
			// jump to point where msb changes
			for (int j = MAX_LOG - 1; j >= 0; j--)
				if (!wrong_turn(at, j, k)) { // doesn't change => jump
					auto& x = dp[at][j][k];
					at = x.end;
					strength += x.gained;
				} // else it changes, so don't jump forward
			// now wrong_turn(at, 0, k) holds, so we win
			strength += s[at];
			at = w[at];
		}
		return strength;
	}
};

// because p[i] = s[i], every time we lose, our strength doubles
// lots of copy-pasta
struct Subtask2 {
	struct {
		int end;
		long long gained;
		long long min; // min(sum(gained) - opponent)
	} dp[MAX_N][MAX_LOG];

	Subtask2() {
		for (int j = 0; j < MAX_LOG; j++)
			for (int i = 0; i <= n; i++) {
				auto& x = dp[i][j];
				if (j == 0)
					if (i == n) {
						x.end = n;
						x.gained = x.min = 0;
					} else {
						x.end = w[i];
						x.gained = s[i];
						x.min = -s[i];
					}
				else {
					auto& a = dp[i][j - 1];
					auto& b = dp[a.end][j - 1];
					x.end = b.end;
					x.gained = a.gained + b.gained;
					x.min = min(a.min, a.gained + b.min);
				}
			}
	}

	long long simulate(int at, long long strength) {
		auto lose = [&](int i, int j) {
			return strength + dp[i][j].min < 0;
		};
		while (at != n) {
			// jump until we lose
			for (int j = MAX_LOG - 1; j >= 0; j--)
				if (!lose(at, j)) {
					auto& x = dp[at][j];
					at = x.end;
					strength += x.gained;
				}
			// lose (if we're at the end, this adds 0)
			strength += p[at]; // = s[at] > strength
			at = l[at];
		}
		return strength;
	}
};

optional<Subtask1345> sub1345;
optional<Subtask2> sub2;

void init(int n_, vector<int> s_, vector<int> p_,
		vector<int> w_, vector<int> l_) {
	n = n_;
	copy_n(s_.begin(), n, s);
	copy_n(p_.begin(), n, p);
	copy_n(w_.begin(), n, w);
	copy_n(l_.begin(), n, l);
	w[n] = l[n] = n;
	if (n > 50000)
		sub2.emplace();
	else
		sub1345.emplace();
}

long long simulate(int at, int s_init) {
	return n > 50000 ? sub2->simulate(at, s_init) :
		sub1345->simulate(at, s_init);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 31 ms 29772 KB Output is correct
4 Correct 1104 ms 736520 KB Output is correct
5 Correct 28 ms 29772 KB Output is correct
6 Correct 1099 ms 737176 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15052 KB Output is correct
2 Correct 641 ms 255384 KB Output is correct
3 Correct 662 ms 261544 KB Output is correct
4 Correct 583 ms 262924 KB Output is correct
5 Correct 586 ms 263116 KB Output is correct
6 Correct 625 ms 261576 KB Output is correct
7 Correct 630 ms 259816 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15052 KB Output is correct
2 Correct 1036 ms 737992 KB Output is correct
3 Correct 1010 ms 738316 KB Output is correct
4 Correct 965 ms 737396 KB Output is correct
5 Correct 1004 ms 737236 KB Output is correct
6 Correct 978 ms 737424 KB Output is correct
7 Correct 1000 ms 737272 KB Output is correct
8 Correct 997 ms 737332 KB Output is correct
9 Correct 985 ms 737268 KB Output is correct
10 Correct 965 ms 737356 KB Output is correct
11 Correct 1103 ms 737252 KB Output is correct
12 Correct 1358 ms 737324 KB Output is correct
13 Correct 1061 ms 737440 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15052 KB Output is correct
2 Correct 1036 ms 737992 KB Output is correct
3 Correct 1010 ms 738316 KB Output is correct
4 Correct 965 ms 737396 KB Output is correct
5 Correct 1004 ms 737236 KB Output is correct
6 Correct 978 ms 737424 KB Output is correct
7 Correct 1000 ms 737272 KB Output is correct
8 Correct 997 ms 737332 KB Output is correct
9 Correct 985 ms 737268 KB Output is correct
10 Correct 965 ms 737356 KB Output is correct
11 Correct 1103 ms 737252 KB Output is correct
12 Correct 1358 ms 737324 KB Output is correct
13 Correct 1061 ms 737440 KB Output is correct
14 Correct 15 ms 15080 KB Output is correct
15 Correct 1046 ms 737324 KB Output is correct
16 Correct 1090 ms 737328 KB Output is correct
17 Correct 985 ms 737352 KB Output is correct
18 Correct 1008 ms 737372 KB Output is correct
19 Correct 1046 ms 737280 KB Output is correct
20 Correct 1004 ms 737328 KB Output is correct
21 Correct 1014 ms 737408 KB Output is correct
22 Correct 921 ms 737252 KB Output is correct
23 Correct 1132 ms 737224 KB Output is correct
24 Correct 1424 ms 737396 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15052 KB Output is correct
2 Correct 1036 ms 737992 KB Output is correct
3 Correct 1010 ms 738316 KB Output is correct
4 Correct 965 ms 737396 KB Output is correct
5 Correct 1004 ms 737236 KB Output is correct
6 Correct 978 ms 737424 KB Output is correct
7 Correct 1000 ms 737272 KB Output is correct
8 Correct 997 ms 737332 KB Output is correct
9 Correct 985 ms 737268 KB Output is correct
10 Correct 965 ms 737356 KB Output is correct
11 Correct 1103 ms 737252 KB Output is correct
12 Correct 1358 ms 737324 KB Output is correct
13 Correct 1061 ms 737440 KB Output is correct
14 Correct 15 ms 15080 KB Output is correct
15 Correct 1046 ms 737324 KB Output is correct
16 Correct 1090 ms 737328 KB Output is correct
17 Correct 985 ms 737352 KB Output is correct
18 Correct 1008 ms 737372 KB Output is correct
19 Correct 1046 ms 737280 KB Output is correct
20 Correct 1004 ms 737328 KB Output is correct
21 Correct 1014 ms 737408 KB Output is correct
22 Correct 921 ms 737252 KB Output is correct
23 Correct 1132 ms 737224 KB Output is correct
24 Correct 1424 ms 737396 KB Output is correct
25 Correct 1008 ms 736548 KB Output is correct
26 Correct 1063 ms 737212 KB Output is correct
27 Correct 1051 ms 737320 KB Output is correct
28 Correct 1059 ms 737400 KB Output is correct
29 Correct 1138 ms 737428 KB Output is correct
30 Correct 1399 ms 737320 KB Output is correct
31 Correct 1359 ms 737348 KB Output is correct
32 Correct 1760 ms 737364 KB Output is correct
33 Correct 1528 ms 736924 KB Output is correct
34 Correct 2933 ms 736968 KB Output is correct
35 Correct 1503 ms 737224 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15052 KB Output is correct
2 Correct 641 ms 255384 KB Output is correct
3 Correct 662 ms 261544 KB Output is correct
4 Correct 583 ms 262924 KB Output is correct
5 Correct 586 ms 263116 KB Output is correct
6 Correct 625 ms 261576 KB Output is correct
7 Correct 630 ms 259816 KB Output is correct
8 Correct 13 ms 15052 KB Output is correct
9 Correct 1036 ms 737992 KB Output is correct
10 Correct 1010 ms 738316 KB Output is correct
11 Correct 965 ms 737396 KB Output is correct
12 Correct 1004 ms 737236 KB Output is correct
13 Correct 978 ms 737424 KB Output is correct
14 Correct 1000 ms 737272 KB Output is correct
15 Correct 997 ms 737332 KB Output is correct
16 Correct 985 ms 737268 KB Output is correct
17 Correct 965 ms 737356 KB Output is correct
18 Correct 1103 ms 737252 KB Output is correct
19 Correct 1358 ms 737324 KB Output is correct
20 Correct 1061 ms 737440 KB Output is correct
21 Correct 15 ms 15080 KB Output is correct
22 Correct 1046 ms 737324 KB Output is correct
23 Correct 1090 ms 737328 KB Output is correct
24 Correct 985 ms 737352 KB Output is correct
25 Correct 1008 ms 737372 KB Output is correct
26 Correct 1046 ms 737280 KB Output is correct
27 Correct 1004 ms 737328 KB Output is correct
28 Correct 1014 ms 737408 KB Output is correct
29 Correct 921 ms 737252 KB Output is correct
30 Correct 1132 ms 737224 KB Output is correct
31 Correct 1424 ms 737396 KB Output is correct
32 Correct 1008 ms 736548 KB Output is correct
33 Correct 1063 ms 737212 KB Output is correct
34 Correct 1051 ms 737320 KB Output is correct
35 Correct 1059 ms 737400 KB Output is correct
36 Correct 1138 ms 737428 KB Output is correct
37 Correct 1399 ms 737320 KB Output is correct
38 Correct 1359 ms 737348 KB Output is correct
39 Correct 1760 ms 737364 KB Output is correct
40 Correct 1528 ms 736924 KB Output is correct
41 Correct 2933 ms 736968 KB Output is correct
42 Correct 1503 ms 737224 KB Output is correct
43 Correct 1 ms 332 KB Output is correct
44 Correct 14 ms 15124 KB Output is correct
45 Correct 602 ms 261900 KB Output is correct
46 Correct 563 ms 260344 KB Output is correct
47 Execution timed out 7076 ms 260404 KB Time limit exceeded
48 Halted 0 ms 0 KB -