Submission #440317

#	Time	Username	Problem	Language	Result	Execution time	Memory
440317		frodakcin	Dungeons Game (IOI21_dungeons)	C++17	89 / 100	7181 ms	1397184 KiB

dungeons

#include "dungeons.h"
#include <cassert>
#include <cstring>
#include <algorithm>
#include <vector>

using ll = long long;

const int MN = 4e5+10;
const int W = 7; // 7 worlds
const int MUL = 16; // multiplier = 16
const int ML = 25; // 2^25 ~ 3e7
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;

int N;
std::vector<int> s, p, w, l;
int jmp[W][MN][ML];
ll delta[W][MN][ML], max[W][MN][ML];

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;

	memset(jmp, -1, sizeof jmp);
	int b=1;
	for(int v=0;v<W;++v)
	{
		for(int i=0;i<N;++i)
			if(s[i] < b)
			{
				jmp[v][i][0]=w[i];
				delta[v][i][0]=s[i];
				max[v][i][0]=INFL;
			}
			else
			{
				jmp[v][i][0]=l[i];
				delta[v][i][0]=p[i];
				max[v][i][0]=s[i]; // >= max -> unexpected; < max -> go ahead
			}
		for(int j=0;j+1<ML;++j)
			for(int i=0;i<N;++i)
				if(jmp[v][i][j]!=-1 && jmp[v][jmp[v][i][j]][j]!=-1)
				{
					int x = jmp[v][i][j];
					jmp[v][i][j+1]=jmp[v][x][j];
					delta[v][i][j+1]=delta[v][i][j]+delta[v][x][j];
					max[v][i][j+1]=std::min(max[v][i][j], max[v][x][j]-delta[v][i][j]);
				}
		b *= MUL;
	}
}

void step(int &n, ll &z)
{
	if(n==N) return;
	if(z<s[n])
		z+=p[n], n=l[n];
	else
		z+=s[n], n=w[n];
}

void jump(int v, int cut, int &n, ll &z)
{
	for(int i=ML-1;i>=0;--i)
		if(jmp[v][n][i] != -1 && z<max[v][n][i] && (cut == -1 || z+delta[v][n][i]<cut)) // while isn't necessary here
			z+=delta[v][n][i], n=jmp[v][n][i];
}

long long simulate(int n, int _z) {
	ll z=_z;

	int b=1;
	for(int i=0;i+1<W;++i)
	{
		b *= MUL;
		while(z<b)
		{
			jump(i, b, n, z);
			step(n, z);
			if(n==N) return z;
		}
	}
	jump(W-1, -1, n, z);

	assert(n==N);
	return z;
}

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