Submission #438342

#	Time	Username	Problem	Language	Result	Execution time	Memory
438342		JustasZ	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	5786 ms	1048580 KiB

dungeons

#include "dungeons.h"
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#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;
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) {
		LOG = 19;
	}

	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;
	for (int grp = 0; grp < LOG - 1; grp++) {
		ll group_lower_bound = 1 << grp;
		if (cur_sum >= group_lower_bound * 2) {
			continue;
		}

		if (cur_sum < group_lower_bound) {
			exit(3);
		}

		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 && cur_sum < group_lower_bound * 2) {
			exit(3);
		}

		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;
}

Compilation message (stderr)

dungeons.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
dungeons.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      |

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