제출 #684068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684068		Asymmetry	던전 (IOI21_dungeons)	C++17	0 / 100	7077 ms	5204 KiB

dungeons

#include<bits/stdc++.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

const int Z = 20;
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);
	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] = INF;
		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] = lim[k][j][jmp[k][j][i]] - add[k][j][i];
			}
		}
	}
}

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;
		for (int i = Z - 1; i >= 0; --i) {
			if (lim[tre][i][pos] >= mass) {
				mass += add[tre][i][pos];
				pos = jmp[tre][i][pos];
			}
		}
		if (mass >= s[pos]) {
			mass += s[pos];
			pos = w[pos];
		}
		else {
			mass += p[pos];
			pos = l[pos];
		}
	}
	return mass;
}

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