oj.uz

Submission #437687

# Submission time Handle Problem Language Result Execution time Memory
437687 2021-06-26T21:22:59 Z ecnerwala Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3604 ms 276352 KB 
#include "dungeons.h"

#include <bits/stdc++.h>

namespace std {

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

} // namespace std

namespace ecnerwala {
const int64_t INF = 1e18;
struct node_t {
	int s, p, w, l;
};
std::vector<node_t> nodes;
struct jump_t {
	int dest;
	int64_t tot;
	int64_t cap;
};
const int LG = 25;
std::array<std::vector<jump_t>, LG> jumps;
};

void init(int N, std::vector<int> S_, std::vector<int> P_, std::vector<int> W_, std::vector<int> L_) {
	using namespace ecnerwala;
	nodes.resize(N);
	for (int i = 0; i < N; i++) {
		nodes[i] = {S_[i], P_[i], W_[i], L_[i]};
	}
	auto merge = [](jump_t a, jump_t b) -> jump_t {
		return jump_t{b.dest, a.tot + b.tot, std::min(a.cap, b.cap - a.tot)};
	};
	auto node_jump = [](int cur, int baseline) -> jump_t {
		if (nodes[cur].s <= baseline) {
			return jump_t{nodes[cur].w, nodes[cur].s, INF};
		} else {
			return jump_t{nodes[cur].l, nodes[cur].p, nodes[cur].s};
		}
	};
	for (int l = 0; l < LG; l++) {
		auto& jump = jumps[l];
		jump.resize(N);
		// Funny thing: we can initialize jumps to the 1-edge jump, and then consider them updated when we set jump_len >= 0
		for (int i = 0; i < N; i++) {
			jump[i] = node_jump(i, 1 << l);
		}
		std::vector<int> jump_len(N+1, -1); // this is for bookkeeping our skew-binary representation
		jump_len[N] = 0;
		auto solve = std::y_combinator([&](auto self, int cur) -> void {
			if (jump_len[cur] >= 0) return;
			if (jump_len[cur] == -2) {
				// we're a cycle
				jump_len[cur] = 0;
				while (jump[cur].dest != cur) {
					assert(jump_len[jump[cur].dest] == -2);
					jump[cur] = merge(jump[cur], jump[jump[cur].dest]);
				}
				assert(jump[cur].dest == cur);
				return;
			}
			jump_len[cur] = -2;
			int nxt = jump[cur].dest;
			self(nxt);
			if (jump_len[cur] == 0) {
				// we're a cycle we found later
				return;
			}
			if (jump_len[nxt] > 0 && jump_len[jump[nxt].dest] == jump_len[nxt]) {
				jump_len[cur] = 1 + 2 * jump_len[nxt];
				jump[cur] = merge(jump[cur], jump[jump[cur].dest]);
				jump[cur] = merge(jump[cur], jump[jump[cur].dest]);
			} else {
				jump_len[cur] = 1;
				// no-op
			}
			assert(jump_len[cur] > 0);
		});
		for (int i = 0; i < N; i++) {
			solve(i);
		}
	}
}

long long simulate(int X, int Z_) {
	using namespace ecnerwala;
	int64_t Z = Z_;
	while (X != int(nodes.size())) {
		assert(Z >= 1);
		int k = std::min<int>(LG-1, 8 * sizeof(Z) - 1 - __builtin_clzll(Z));
		jump_t j = jumps[k][X];
		if (Z < j.cap) {
			if (j.dest == X) {
				// let's go for as many cycles as necessary
				Z += (j.cap - 1 - Z) / j.tot * j.tot;
			}
			Z += j.tot;
			X = j.dest;
		} else {
			// just walk forwards by 1
			node_t n = nodes[X];
			if (Z >= n.s) {
				Z += n.s;
				X = n.w;
			} else {
				Z += n.p;
				X = n.l;
			}
		}
	}
	return Z;
}

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 204 KB Output is correct
3 Correct 4 ms 1484 KB Output is correct
4 Correct 109 ms 32732 KB Output is correct
5 Correct 4 ms 1576 KB Output is correct
6 Correct 102 ms 32740 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 972 KB Output is correct
2 Correct 867 ms 269488 KB Output is correct
3 Correct 839 ms 276352 KB Output is correct
4 Correct 911 ms 276332 KB Output is correct
5 Correct 1250 ms 257556 KB Output is correct
6 Correct 899 ms 269732 KB Output is correct
7 Correct 827 ms 276160 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 972 KB Output is correct
2 Correct 121 ms 33556 KB Output is correct
3 Correct 124 ms 35276 KB Output is correct
4 Correct 125 ms 35836 KB Output is correct
5 Correct 108 ms 35060 KB Output is correct
6 Correct 152 ms 33536 KB Output is correct
7 Correct 167 ms 33792 KB Output is correct
8 Correct 118 ms 35972 KB Output is correct
9 Correct 136 ms 33756 KB Output is correct
10 Correct 127 ms 35824 KB Output is correct
11 Correct 127 ms 35960 KB Output is correct
12 Correct 237 ms 36136 KB Output is correct
13 Correct 142 ms 36224 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 972 KB Output is correct
2 Correct 121 ms 33556 KB Output is correct
3 Correct 124 ms 35276 KB Output is correct
4 Correct 125 ms 35836 KB Output is correct
5 Correct 108 ms 35060 KB Output is correct
6 Correct 152 ms 33536 KB Output is correct
7 Correct 167 ms 33792 KB Output is correct
8 Correct 118 ms 35972 KB Output is correct
9 Correct 136 ms 33756 KB Output is correct
10 Correct 127 ms 35824 KB Output is correct
11 Correct 127 ms 35960 KB Output is correct
12 Correct 237 ms 36136 KB Output is correct
13 Correct 142 ms 36224 KB Output is correct
14 Correct 3 ms 972 KB Output is correct
15 Correct 124 ms 33792 KB Output is correct
16 Correct 127 ms 33832 KB Output is correct
17 Correct 114 ms 34696 KB Output is correct
18 Correct 116 ms 34612 KB Output is correct
19 Correct 150 ms 33408 KB Output is correct
20 Correct 145 ms 34816 KB Output is correct
21 Correct 134 ms 34820 KB Output is correct
22 Correct 127 ms 34816 KB Output is correct
23 Correct 132 ms 35076 KB Output is correct
24 Correct 270 ms 35680 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 972 KB Output is correct
2 Correct 121 ms 33556 KB Output is correct
3 Correct 124 ms 35276 KB Output is correct
4 Correct 125 ms 35836 KB Output is correct
5 Correct 108 ms 35060 KB Output is correct
6 Correct 152 ms 33536 KB Output is correct
7 Correct 167 ms 33792 KB Output is correct
8 Correct 118 ms 35972 KB Output is correct
9 Correct 136 ms 33756 KB Output is correct
10 Correct 127 ms 35824 KB Output is correct
11 Correct 127 ms 35960 KB Output is correct
12 Correct 237 ms 36136 KB Output is correct
13 Correct 142 ms 36224 KB Output is correct
14 Correct 3 ms 972 KB Output is correct
15 Correct 124 ms 33792 KB Output is correct
16 Correct 127 ms 33832 KB Output is correct
17 Correct 114 ms 34696 KB Output is correct
18 Correct 116 ms 34612 KB Output is correct
19 Correct 150 ms 33408 KB Output is correct
20 Correct 145 ms 34816 KB Output is correct
21 Correct 134 ms 34820 KB Output is correct
22 Correct 127 ms 34816 KB Output is correct
23 Correct 132 ms 35076 KB Output is correct
24 Correct 270 ms 35680 KB Output is correct
25 Correct 107 ms 32552 KB Output is correct
26 Correct 134 ms 33388 KB Output is correct
27 Correct 137 ms 33376 KB Output is correct
28 Correct 118 ms 33324 KB Output is correct
29 Correct 144 ms 33348 KB Output is correct
30 Correct 178 ms 35580 KB Output is correct
31 Correct 203 ms 35716 KB Output is correct
32 Correct 245 ms 35592 KB Output is correct
33 Correct 230 ms 35456 KB Output is correct
34 Correct 497 ms 33408 KB Output is correct
35 Correct 254 ms 34192 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 972 KB Output is correct
2 Correct 867 ms 269488 KB Output is correct
3 Correct 839 ms 276352 KB Output is correct
4 Correct 911 ms 276332 KB Output is correct
5 Correct 1250 ms 257556 KB Output is correct
6 Correct 899 ms 269732 KB Output is correct
7 Correct 827 ms 276160 KB Output is correct
8 Correct 3 ms 972 KB Output is correct
9 Correct 121 ms 33556 KB Output is correct
10 Correct 124 ms 35276 KB Output is correct
11 Correct 125 ms 35836 KB Output is correct
12 Correct 108 ms 35060 KB Output is correct
13 Correct 152 ms 33536 KB Output is correct
14 Correct 167 ms 33792 KB Output is correct
15 Correct 118 ms 35972 KB Output is correct
16 Correct 136 ms 33756 KB Output is correct
17 Correct 127 ms 35824 KB Output is correct
18 Correct 127 ms 35960 KB Output is correct
19 Correct 237 ms 36136 KB Output is correct
20 Correct 142 ms 36224 KB Output is correct
21 Correct 3 ms 972 KB Output is correct
22 Correct 124 ms 33792 KB Output is correct
23 Correct 127 ms 33832 KB Output is correct
24 Correct 114 ms 34696 KB Output is correct
25 Correct 116 ms 34612 KB Output is correct
26 Correct 150 ms 33408 KB Output is correct
27 Correct 145 ms 34816 KB Output is correct
28 Correct 134 ms 34820 KB Output is correct
29 Correct 127 ms 34816 KB Output is correct
30 Correct 132 ms 35076 KB Output is correct
31 Correct 270 ms 35680 KB Output is correct
32 Correct 107 ms 32552 KB Output is correct
33 Correct 134 ms 33388 KB Output is correct
34 Correct 137 ms 33376 KB Output is correct
35 Correct 118 ms 33324 KB Output is correct
36 Correct 144 ms 33348 KB Output is correct
37 Correct 178 ms 35580 KB Output is correct
38 Correct 203 ms 35716 KB Output is correct
39 Correct 245 ms 35592 KB Output is correct
40 Correct 230 ms 35456 KB Output is correct
41 Correct 497 ms 33408 KB Output is correct
42 Correct 254 ms 34192 KB Output is correct
43 Correct 1 ms 204 KB Output is correct
44 Correct 3 ms 972 KB Output is correct
45 Correct 1835 ms 257456 KB Output is correct
46 Correct 1255 ms 257060 KB Output is correct
47 Correct 1489 ms 257268 KB Output is correct
48 Correct 1226 ms 269928 KB Output is correct
49 Correct 1651 ms 257552 KB Output is correct
50 Correct 955 ms 269532 KB Output is correct
51 Correct 1022 ms 266532 KB Output is correct
52 Correct 911 ms 269532 KB Output is correct
53 Correct 2629 ms 275812 KB Output is correct
54 Correct 1316 ms 266216 KB Output is correct
55 Correct 1699 ms 257968 KB Output is correct
56 Correct 2013 ms 271136 KB Output is correct
57 Correct 1946 ms 272412 KB Output is correct
58 Correct 1900 ms 269484 KB Output is correct
59 Correct 2393 ms 271272 KB Output is correct
60 Correct 3331 ms 263544 KB Output is correct
61 Correct 3604 ms 271696 KB Output is correct