Submission #1079744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079744		GusterGoose27	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	394 ms	736532 KiB

dungeons

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

using namespace std;
typedef long long ll;

const int MAXN = 5e4+5;//4e5+5;
const ll MAXS = 1e18;;
const int MAXB = 25; // will always terminate after 2^24 steps
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];
			}
		}
	}
	step(step &a, step &b) {
		st = min(MAXS, a.st+b.st);
		f = b.f;
		m = min(a.m, b.m-a.st);
	}
};

step lift[MAXB][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; c++) {
		for (int i = 0; i < n; i++) lift[c][0][i] = step(i, c);
		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]);
		}
	}
}

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

ll simulate(int x, int z) {
	return simulate2(x, z);
}

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