제출 #442233

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

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define fir first
#define sec second
typedef long long ll;
using namespace std;

int N;
vector<int> S,P,W,L;
pair<ll,ll> jump[6][31][400005];

set<int> mys;
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;

	for(int i=0;i<n;i++) mys.insert(s[i]);
	mys.insert(0);

	int cnt = 0;
	for(auto x:mys)
	{
		for(int i=0;i<n;i++) 
		{
			if(s[i]<=x) jump[cnt][0][i] = {s[i],w[i]}; //if win
			else jump[cnt][0][i] = {p[i],l[i]}; //if lose
		}
		jump[cnt][0][n] = {0,n};

		for(int i=1;i<=30;i++)
		{
			for(int j=0;j<=n;j++)
			{
				jump[cnt][i][j] = {jump[cnt][i-1][j].fir+jump[cnt][i-1][jump[cnt][i-1][j].sec].fir,
								jump[cnt][i-1][jump[cnt][i-1][j].sec].sec};
			}
		}
		cnt++;
	}
	return;
}

ll simulate(int x, int z) 
{
	int pos = x;
	ll str = z;

	int cnt = 0;
	for(auto itr=mys.begin();itr!=mys.end();itr++)
	{
		int nxt;
		if((++itr)!=mys.end()) nxt = *(itr),itr--;
		else break;

		for(int i=30;i>=0;i--)
		{
			if(str+jump[cnt][i][pos].fir<nxt)
			{	
				str += jump[cnt][i][pos].fir;
				pos = jump[cnt][i][pos].sec;
			}
		}

		while(pos!=N)
		{
			if(str>=nxt) break;
			else if(str>=S[pos]) str += S[pos], pos = W[pos];
			else str += P[pos], pos = L[pos];
		}

		cnt++;
	}

	for(int i=30;i>=0;i--)
	{
		str += jump[cnt][i][pos].fir;
		pos = jump[cnt][i][pos].sec;
	}
	if(pos!=N) str += jump[cnt][0][pos].fir;
	return str;
}

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