제출 #443334

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
443334		JvThunder	던전 (IOI21_dungeons)	C++17	100 / 100	4197 ms	699540 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define fir first
#define sec second
typedef long long ll;
using namespace std;
  
int base = 8;
const int nop = 3;
const int noa = 24;
const int sz = 400005;
ll INF = 1e9+7;
 
pair<ll,pair<ll,ll>> jump[sz][nop][noa];
ll add[sz];

int N;
vector<int> S,P,W,L;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) 
{
	S = s; P = p; W = w; L = l; N = n;
	S.push_back(INF);
	P.push_back(INF);
	W.push_back(n);
	L.push_back(n);
	
	add[n] = 0;
	for(int i = n-1; i >= 0; i--) add[i] = add[W[i]] + S[i];

	for(int a=0; a<nop; a++) 
	{
		ll l = 1<<(base*a);
		ll r = 1<<(base*(a+1));
		for(int i=0; i<=n; i++) 
		{
			if ((l<S[i] && S[i]<r) || i==n) jump[i][a][0] = {L[i], {S[i], P[i]}};
			else if (S[i]<=l) jump[i][a][0] = {W[i], {INF, S[i]}};
			else jump[i][a][0] = {L[i], {INF, P[i]}};
		}
		
		for(int b=1; b<noa; b++)
		{
			for (int i=0; i<=n; i++)
			{
				int j = i;
				ll min_S = INF, str_add = 0;
				for (int it=0; it<2; it++) 
				{
					auto pr = jump[j][a][b-1];
					min_S = min(min_S, pr.sec.fir - str_add);
					str_add += pr.sec.sec;
					j = pr.first;
				}
				jump[i][a][b] = {j, {min_S, str_add}};
			}
		}
	}
	return;
}
 
ll simulate(int x, int z) 
{
	ll pos = x;
	ll str = z;

	for(int a=0; a<nop; a++)
	{
		ll l = 1<<(base*a);
		ll r = 1<<(base*(a+1));
		while(pos!=N && l<=str && str<r) 
		{
			for (int b=noa-1; b>=0; b--)
			{
				while(str < jump[pos][a][b].sec.fir && str+jump[pos][a][b].sec.sec < r) 
				{
					str += jump[pos][a][b].sec.sec;
					pos = jump[pos][a][b].fir;
				}
			}
			if(pos!=N)
			{
				if(str>=S[pos]) str += S[pos], pos = W[pos];
				else str += P[pos], pos = L[pos];
			}
		}
	}

	str += add[pos];
	return str;
}

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