Submission #1079771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079771		GusterGoose27	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3851 ms	1675484 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 4e5+5;//4e5+5;
const ll MAXS = 1e18;
const int MAXB = 25; // will always terminate after 2^24 steps
const int sskip = 4;
vector<int> s, p, w, l;
int n;

struct step {
	ll st, m; int f; // strength_gain, final, min to beat
	step() {}
	step(int i, int b) { // bucket id
		if (i == n) {
			st = 0;
			f = n;
			m = MAXS;
		}
		else {
			int lcut = (1<<b);
			if (lcut >= s[i]) {
				st = s[i];
				f = w[i];
				m = MAXS;
			}
			else {
				st = p[i];
				f = l[i];
				m = s[i];
			}
		}
		// if (i == 24 && b == 9) cerr << "1 " << m << '\n';
		// assert(m != 0);
		// assert(f <= n);
	}
	step(step &a, step &b) {
		st = min(MAXS, a.st+b.st);
		f = b.f;
		// m = min(a.m, (int)max(0ll, b.m-a.st));
		m = min(a.m, max(0ll, b.m-a.st));
		// assert(f <= n);
	}
};

step lift[MAXB/sskip+1][MAXB][MAXN]; // cutoff, lift num, start

void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
	n = N;
	s = S;
	p = P;
	w = W;
	l = L;
	for (int c = 0; c <= MAXB/sskip; c++) {
		for (int i = 0; i <= n; i++) lift[c][0][i] = step(i, sskip*c);
		// if (c == 9) cerr << lift[9][0][24].m << '\n';
		for (int b = 1; b < MAXB; b++) {
			for (int i = 0; i <= n; i++) lift[c][b][i] = step(lift[c][b-1][i], lift[c][b-1][lift[c][b-1][i].f]);
		}
	}
	// cerr << lift[9][0][24].m << '\n';
}

ll simulate2(int x, ll z) {
	// cerr << x << ' ' << z << '\n';
	assert(x <= n);
	if (x == n) return z;
	int c = (z >= (1ll<<(MAXB-1)) ? MAXB-1 :  31-__builtin_clz(z));
	// cerr << c << ' ' << z << '\n';
	if (c == MAXB-1) return lift[c/sskip][MAXB-1][x].st + z;
	for (int b = MAXB-1; b >= 0; b--) {
		if (z < lift[c/sskip][b][x].m) return simulate2(lift[c/sskip][b][x].f, lift[c/sskip][b][x].st+z);
	}
	// if (z < s[x]) return -1;
	// if (z < s[x]) {
	// 	cerr << c << ' ' << z << ' ' << n << ' ' << x << '\n';
	// 	cerr << lift[c][0][x].m << ' ' << s[x] << '\n';
	// 	assert(false);
	// }
	assert(z >= s[x]);
	return simulate2(w[x], z + s[x]);
}

ll simulate(int x, int z) {
	// cerr << lift[9][0][24].m << '\n';
	return simulate2(x, z);
}

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