Submission #797990

#	Time	Username	Problem	Language	Result	Execution time	Memory
797990		iee	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2314 ms	1148364 KiB

dungeons

#pragma GCC optimize("Ofast")
#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
constexpr int Base = 26, LN = 25, LS = 6, N = 4e5 + 5;
using ll = long long;
constexpr ll inf = 1e18;
int n;
int go[LS][LN][N];
ll lim[LS][LN][N], gain[LS][LN][N], pw[LS];
vector<int> s, p, win, lose;
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, win = W, lose = L;
	for (int i = pw[0] = 1; i < LS; i++) {
		pw[i] = pw[i - 1] * Base;
	}
	for (int C = 0; C < LS; C++) {
		for (int i = 0; i < n; i++) {
			if (pw[C] >= s[i]) {
				if (win[i] == n) {
					go[C][0][i] = -1;
				} else {
					go[C][0][i] = win[i];
					gain[C][0][i] = s[i];
					lim[C][0][i] = inf;
				}
			} else {
				if (lose[i] == n) {
					go[C][0][i] = -1;
				} else {
					go[C][0][i] = lose[i];
					gain[C][0][i] = p[i];
					lim[C][0][i] = s[i];
				}
			}
		}
	}
	for (int C = 0; C < LS; C++) {
		for (int j = 1; j < LN; j++) {
			for (int i = 0; i < n; i++) {
				if (go[C][j - 1][i] == -1 || go[C][j - 1][go[C][j - 1][i]] == -1) {
					go[C][j][i] = -1;
					continue;
				}
				go[C][j][i] = go[C][j - 1][go[C][j - 1][i]];
				gain[C][j][i] = gain[C][j - 1][i] + gain[C][j - 1][go[C][j - 1][i]];
				lim[C][j][i] = min(lim[C][j - 1][i], lim[C][j - 1][go[C][j - 1][i]] - gain[C][j - 1][i]);
			}
		}
	}
}

long long simulate(int x, int z) {
	long long str = z, c = 0;
	while (x != n) {
		while (c + 1 < LS && pw[c + 1] <= str) c++;
		for (int i = LN - 1; i >= 0; i--) {
			if (go[c][i][x] == -1) continue;
			if (str < lim[c][i][x]) {
				str += gain[c][i][x];
				x = go[c][i][x];
			}
		}
		if (str >= s[x]) str += s[x], x = win[x];
		else str += p[x], x = lose[x];
	}
	return str;
}

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11