Submission #438398

#	Time	Username	Problem	Language	Result	Execution time	Memory
438398		JustasZ	Dungeons Game (IOI21_dungeons)	C++17	89 / 100	5916 ms	458796 KiB

dungeons

#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 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 0 / 11