oj.uz

Submission #438398

# Submission time Handle Problem Language Result Execution time Memory
438398 2021-06-27T22:28:40 Z JustasZ Dungeons Game (IOI21_dungeons) C++17
89 / 100
 5916 ms 458796 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define rd() abs((int)rng())
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int LOG = 25;
vector<vector<vector<ll> > >sum;
vector<vector<vector<ll> > >mn;
vector<vector<vector<int> > >jump;

vector<vector<ll> >SUM;
vector<vector<ll> >MX;
vector<vector<int> >JUMP;
int n;
vector<int>s, p, w, l;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
	n = N;
	s = S, p = P, w = W, l = L;
	s.pb(0);
	p.pb(0);
	w.pb(0);
	l.pb(0);
	w[n] = n;

	if (n > 50000) {
		SUM = vector<vector<ll> >(LOG, vector<ll>(n + 1));
		MX = vector<vector<ll> >(LOG, vector<ll>(n + 1, -1e18));
		JUMP = vector<vector<int> >(LOG, vector<int>(n + 1, -1));

		for (int jmp = 0; jmp < LOG; jmp++) {
			for (int i = 0; i < n; i++) {
				if (jmp == 0) {
					SUM[0][i] = s[i];
					MX[0][i] = s[i];
					JUMP[0][i] = w[i];
				} else {
					int x = JUMP[jmp - 1][i];
					if (x != -1) {
						SUM[jmp][i] = SUM[jmp - 1][i] + SUM[jmp - 1][x];
						MX[jmp][i] = max(MX[jmp - 1][i], MX[jmp - 1][x] - SUM[jmp - 1][i]);
						JUMP[jmp][i] = JUMP[jmp - 1][x];
					} else {
						JUMP[jmp][i] = -1;
					}
				}
			}
		}
		return;
	}

	sum = vector<vector<vector<ll> > >(LOG, vector<vector<ll> >(n + 1));
	mn = vector<vector<vector<ll> > >(LOG, vector<vector<ll> >(n + 1));
	jump = vector<vector<vector<int> > >(LOG, vector<vector<int> >(n + 1));
 
	for (int grp = 0; grp < LOG; grp++) {
		for (int i = 0; i <= n; i++) {
			sum[grp][i] = vector<ll>(grp + 1, 0);
			mn[grp][i] = vector<ll>(grp + 1, 1e18);
			jump[grp][i] = vector<int>(grp + 1, -1);
		}
	}
 
	for (int grp = 0; grp < LOG; grp++) {
		int upto = 1 << grp;
		for (int jmp = 0; jmp < grp; jmp++) {
			for (int i = 0; i < n; i++) {
				if (jmp == 0) {
					int to;
					if (s[i] <= upto) { // definitely win
						sum[grp][i][0] = s[i];
						to = w[i];
					} else { // might win
						sum[grp][i][0] = p[i];
						mn[grp][i][0] = s[i];
						to = l[i];
					}
 
					jump[grp][i][0] = to;
				} else {
					int x = jump[grp][i][jmp - 1];
					if (x != -1) {
						sum[grp][i][jmp] = sum[grp][i][jmp - 1] + sum[grp][x][jmp - 1];
						mn[grp][i][jmp] = min(mn[grp][i][jmp - 1], mn[grp][x][jmp - 1] - sum[grp][i][jmp - 1]);
						jump[grp][i][jmp] = jump[grp][x][jmp - 1];
					} else {
						jump[grp][i][jmp] = -1;
					}
				}
			}
		}
	}
}
 
ll simulate(int x, int z) {
	ll cur_sum = z;
	int cur = x;

	if (n > 50000) {
		while (true) {
			for (int jmp = LOG - 1; jmp >= 0; jmp--) {
				if (JUMP[jmp][cur] != -1 && JUMP[jmp][cur] != n && MX[jmp][cur] <= cur_sum) {
					cur_sum += SUM[jmp][cur];
					cur = JUMP[jmp][cur];
				}
			}

			ll was_sum = cur_sum;
			if (cur_sum >= s[cur]) {
				cur_sum += s[cur];
				cur = w[cur];
			} else {
				cur_sum += p[cur];
				cur = l[cur];
			}

			if (cur == n) {
				return cur_sum;
			} else {
				assert(cur_sum >= was_sum * 2);
			}
		}
	}

	for (int grp = 0; grp < LOG - 1; grp++) {
		ll group_lower_bound = 1 << grp;
		if (cur_sum >= group_lower_bound * 2) {
			continue;
		}
 
		for (int jmp = grp; jmp >= 0; jmp--) {
			if (jump[grp][cur][jmp] != -1 
			&& (cur_sum + sum[grp][cur][jmp] < group_lower_bound * 2)
			&& (cur_sum < mn[grp][cur][jmp])) {
				cur_sum += sum[grp][cur][jmp];
				cur = jump[grp][cur][jmp];
			}
		}
 
		if (cur_sum >= s[cur]) {
			cur_sum += s[cur];
			cur = w[cur];
		} else {
			cur_sum += p[cur];
			cur = l[cur];
		}
 
		if (cur == n) {
			return cur_sum;
		}
	}
 
	for (int jmp = LOG - 1; jmp >= 0; jmp--) {
		if (jump[LOG - 1][cur][jmp] != -1 && jump[LOG - 1][cur][jmp] != n) {
			cur_sum += sum[LOG - 1][cur][jmp];
			cur = jump[LOG - 1][cur][jmp];
		}
	}
 
	if (cur_sum >= s[cur]) {
		cur_sum += s[cur];
		cur = w[cur];
	} else {
		cur_sum += p[cur];
		cur = l[cur];
	}
 
	return cur_sum;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 28 ms 18560 KB Output is correct
4 Correct 954 ms 457852 KB Output is correct
5 Correct 29 ms 18508 KB Output is correct
6 Correct 900 ms 457920 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 9420 KB Output is correct
2 Correct 440 ms 218752 KB Output is correct
3 Correct 432 ms 221592 KB Output is correct
4 Correct 445 ms 222488 KB Output is correct
5 Correct 434 ms 222232 KB Output is correct
6 Correct 497 ms 221444 KB Output is correct
7 Correct 448 ms 221052 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9488 KB Output is correct
2 Correct 1240 ms 458668 KB Output is correct
3 Correct 1198 ms 458548 KB Output is correct
4 Correct 1068 ms 458660 KB Output is correct
5 Correct 1119 ms 458584 KB Output is correct
6 Correct 1519 ms 458784 KB Output is correct
7 Correct 1620 ms 458664 KB Output is correct
8 Correct 1822 ms 458728 KB Output is correct
9 Correct 910 ms 458660 KB Output is correct
10 Correct 1649 ms 458704 KB Output is correct
11 Correct 2816 ms 458788 KB Output is correct
12 Correct 5916 ms 458628 KB Output is correct
13 Correct 5126 ms 458664 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9488 KB Output is correct
2 Correct 1240 ms 458668 KB Output is correct
3 Correct 1198 ms 458548 KB Output is correct
4 Correct 1068 ms 458660 KB Output is correct
5 Correct 1119 ms 458584 KB Output is correct
6 Correct 1519 ms 458784 KB Output is correct
7 Correct 1620 ms 458664 KB Output is correct
8 Correct 1822 ms 458728 KB Output is correct
9 Correct 910 ms 458660 KB Output is correct
10 Correct 1649 ms 458704 KB Output is correct
11 Correct 2816 ms 458788 KB Output is correct
12 Correct 5916 ms 458628 KB Output is correct
13 Correct 5126 ms 458664 KB Output is correct
14 Correct 15 ms 9500 KB Output is correct
15 Correct 1171 ms 458636 KB Output is correct
16 Correct 1268 ms 458664 KB Output is correct
17 Correct 1413 ms 458732 KB Output is correct
18 Correct 1405 ms 458640 KB Output is correct
19 Correct 1537 ms 458692 KB Output is correct
20 Correct 1526 ms 458632 KB Output is correct
21 Correct 1750 ms 458676 KB Output is correct
22 Correct 1910 ms 458744 KB Output is correct
23 Correct 3229 ms 458664 KB Output is correct
24 Correct 3144 ms 458644 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9488 KB Output is correct
2 Correct 1240 ms 458668 KB Output is correct
3 Correct 1198 ms 458548 KB Output is correct
4 Correct 1068 ms 458660 KB Output is correct
5 Correct 1119 ms 458584 KB Output is correct
6 Correct 1519 ms 458784 KB Output is correct
7 Correct 1620 ms 458664 KB Output is correct
8 Correct 1822 ms 458728 KB Output is correct
9 Correct 910 ms 458660 KB Output is correct
10 Correct 1649 ms 458704 KB Output is correct
11 Correct 2816 ms 458788 KB Output is correct
12 Correct 5916 ms 458628 KB Output is correct
13 Correct 5126 ms 458664 KB Output is correct
14 Correct 15 ms 9500 KB Output is correct
15 Correct 1171 ms 458636 KB Output is correct
16 Correct 1268 ms 458664 KB Output is correct
17 Correct 1413 ms 458732 KB Output is correct
18 Correct 1405 ms 458640 KB Output is correct
19 Correct 1537 ms 458692 KB Output is correct
20 Correct 1526 ms 458632 KB Output is correct
21 Correct 1750 ms 458676 KB Output is correct
22 Correct 1910 ms 458744 KB Output is correct
23 Correct 3229 ms 458664 KB Output is correct
24 Correct 3144 ms 458644 KB Output is correct
25 Correct 1168 ms 457896 KB Output is correct
26 Correct 1298 ms 458688 KB Output is correct
27 Correct 1136 ms 458536 KB Output is correct
28 Correct 1097 ms 458660 KB Output is correct
29 Correct 1305 ms 458664 KB Output is correct
30 Correct 1675 ms 458640 KB Output is correct
31 Correct 1816 ms 458796 KB Output is correct
32 Correct 2228 ms 458660 KB Output is correct
33 Correct 2033 ms 458460 KB Output is correct
34 Correct 3447 ms 458540 KB Output is correct
35 Correct 2081 ms 458656 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 9420 KB Output is correct
2 Correct 440 ms 218752 KB Output is correct
3 Correct 432 ms 221592 KB Output is correct
4 Correct 445 ms 222488 KB Output is correct
5 Correct 434 ms 222232 KB Output is correct
6 Correct 497 ms 221444 KB Output is correct
7 Correct 448 ms 221052 KB Output is correct
8 Correct 15 ms 9488 KB Output is correct
9 Correct 1240 ms 458668 KB Output is correct
10 Correct 1198 ms 458548 KB Output is correct
11 Correct 1068 ms 458660 KB Output is correct
12 Correct 1119 ms 458584 KB Output is correct
13 Correct 1519 ms 458784 KB Output is correct
14 Correct 1620 ms 458664 KB Output is correct
15 Correct 1822 ms 458728 KB Output is correct
16 Correct 910 ms 458660 KB Output is correct
17 Correct 1649 ms 458704 KB Output is correct
18 Correct 2816 ms 458788 KB Output is correct
19 Correct 5916 ms 458628 KB Output is correct
20 Correct 5126 ms 458664 KB Output is correct
21 Correct 15 ms 9500 KB Output is correct
22 Correct 1171 ms 458636 KB Output is correct
23 Correct 1268 ms 458664 KB Output is correct
24 Correct 1413 ms 458732 KB Output is correct
25 Correct 1405 ms 458640 KB Output is correct
26 Correct 1537 ms 458692 KB Output is correct
27 Correct 1526 ms 458632 KB Output is correct
28 Correct 1750 ms 458676 KB Output is correct
29 Correct 1910 ms 458744 KB Output is correct
30 Correct 3229 ms 458664 KB Output is correct
31 Correct 3144 ms 458644 KB Output is correct
32 Correct 1168 ms 457896 KB Output is correct
33 Correct 1298 ms 458688 KB Output is correct
34 Correct 1136 ms 458536 KB Output is correct
35 Correct 1097 ms 458660 KB Output is correct
36 Correct 1305 ms 458664 KB Output is correct
37 Correct 1675 ms 458640 KB Output is correct
38 Correct 1816 ms 458796 KB Output is correct
39 Correct 2228 ms 458660 KB Output is correct
40 Correct 2033 ms 458460 KB Output is correct
41 Correct 3447 ms 458540 KB Output is correct
42 Correct 2081 ms 458656 KB Output is correct
43 Correct 1 ms 332 KB Output is correct
44 Correct 17 ms 9528 KB Output is correct
45 Runtime error 604 ms 433620 KB Execution killed with signal 6
46 Halted 0 ms 0 KB -