Submission #684086

#	Time	Username	Problem	Language	Result	Execution time	Memory
684086		Asymmetry	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7098 ms	1939940 KiB

dungeons

#include<bits/stdc++.h>
#include "dungeons.h"
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...)<<'\n';}(x)
#else
#define debug(...) {}
#endif

#ifdef LOCAL
const int Z = 4;
#else
const int Z = 20;
#endif

const int INF = 1e9;
int n;
vector<int> pot, s, p, w, l;
vector<vector<vector<int>>> jmp, add, lim;

void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
	n = nn;
	s = ss;
	p = pp;
	w = ww;
	l = ll;
	w.emplace_back(n);
	l.emplace_back(n);
	s.emplace_back(0);
	p.emplace_back(0);
	debug(n, s, p, w, l);
	pot = vector (Z, 1);
	REP (i, Z - 1)
		pot[i + 1] = pot[i] << 1;
	jmp = add = lim = vector(Z, vector(Z, vector(n + 1, 0)));
	REP (k, Z) {
		REP (i, n) {
			if (s[i] <= pot[k]) {
				jmp[k][0][i] = w[i];
				add[k][0][i] = s[i];
				lim[k][0][i] = INF;
			}
			else {
				jmp[k][0][i] = l[i];
				add[k][0][i] = p[i];
				lim[k][0][i] = s[i] - 1;
			}
		}
		jmp[k][0][n] = n;
		add[k][0][n] = 0;
		lim[k][0][n] = -1;
		REP (j, Z - 1) {
			REP (i, n + 1) {
				jmp[k][j + 1][i] = jmp[k][j][jmp[k][j][i]];
				add[k][j + 1][i] = add[k][j][i] + add[k][j][jmp[k][j][i]];
				lim[k][j + 1][i] = min(lim[k][j][i], lim[k][j][jmp[k][j][i]] - add[k][j][i]);
			}
		}
	}
	REP (k, Z)
		REP (j, Z)
			debug(k, j, jmp[k][j], add[k][j], lim[k][j]);
}

LL simulate(int x, int z) {
	int pos = x, tre = 0;
	LL mass = z;
	while (pos != n) {
		while (tre + 1 < Z && pot[tre + 1] <= mass)
			++tre;
		debug(tre, mass, pos);
		for (int i = Z - 1; i >= 0; --i) {
			if (lim[tre][i][pos] >= mass) {
				debug("GO", tre, i, pos, mass, lim[tre][i][pos]);
				mass += add[tre][i][pos];
				pos = jmp[tre][i][pos];
				debug("NEW", tre, i, pos, mass);
			}
		}
		if (mass >= s[pos]) {
			mass += s[pos];
			pos = w[pos];
		}
		else {
			mass += p[pos];
			pos = l[pos];
		}
	}
	return mass;
}

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