Submission #826543

#	Time	Username	Problem	Language	Result	Execution time	Memory
826543		arnold518	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	1704 ms	640208 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e4;
const ll INF = 1e18;

int N;
int S[MAXN+10], P[MAXN+10], W[MAXN+10], L[MAXN+10];

ll A[30][30][MAXN+10], B[30][30][MAXN+10];
int C[30][30][MAXN+10];

void init(int _N, vector<int> _S, vector<int> _P, vector<int> _W, vector<int> _L)
{
	N=_N;
	for(int i=1; i<=N; i++)
	{
		S[i]=_S[i-1]; P[i]=_P[i-1];
		W[i]=_W[i-1]+1; L[i]=_L[i-1]+1;
	}

	for(int i=0; i<=23; i++)
	{
		for(int j=1; j<=N; j++)
		{
			if(S[j]<(1<<i)) A[i][0][j]=S[j], B[i][0][j]=(1<<(i+1)), C[i][0][j]=W[j];
			else if(S[j]<(1<<(i+1))) A[i][0][j]=P[j], B[i][0][j]=min((1<<(i+1)), S[j]), C[i][0][j]=L[j];
			else A[i][0][j]=P[j], B[i][0][j]=(1<<(i+1)), C[i][0][j]=L[j];
		}
		A[i][0][N+1]=0, B[i][0][N+1]=0; C[i][0][N+1]=N+1;

		for(int j=1; j<=25; j++)
		{
			for(int k=1; k<=N+1; k++)
			{
				C[i][j][k]=C[i][j-1][C[i][j-1][k]];
				A[i][j][k]=A[i][j-1][k]+A[i][j-1][C[i][j-1][k]];
				B[i][j][k]=min(B[i][j-1][k], B[i][j-1][C[i][j-1][k]]-A[i][j-1][k]);
			}
		}
	}

	for(int i=1; i<=N; i++) A[24][0][i]=S[i], B[24][0][i]=INF, C[24][0][i]=W[i];
	A[24][0][N+1]=0, B[24][0][N+1]=0; C[24][0][N+1]=N+1;
	for(int j=1; j<=25; j++)
	{
		for(int k=1; k<=N+1; k++)
		{	
			int i=24;
			C[i][j][k]=C[i][j-1][C[i][j-1][k]];
			A[i][j][k]=A[i][j-1][k]+A[i][j-1][C[i][j-1][k]];
			B[i][j][k]=min(B[i][j-1][k], B[i][j-1][C[i][j-1][k]]-A[i][j-1][k]);
		}
	}
}

ll simulate(int now, int _x)
{
	now++;
	ll x=_x;

	for(int i=0; i<=24; i++)
	{
		if(x>=(1<<(i+1))) continue;
		for(int j=25; j>=0; j--)
		{
			if(x<B[i][j][now])
			{
				x+=A[i][j][now];
				now=C[i][j][now];
			}
		}
		if(now>N) break;
		if(x<(1<<(i+1)))
		{
			if(x>=S[now]) x+=S[now], now=W[now];
			else x+=P[now], now=L[now];
		}
		assert(x>=(1<<(i+1)));
	}
	return x;
}

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