제출 #645195

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
645195		jamezzz	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2809 ms	730564 KiB

dungeons

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

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

typedef long long ll;

#define maxn 400001
#define lgn 9
#define base 6
#define INF 1023456789123456789

int n,to[lgn+1][lgn][maxn];
ll gain[lgn+1][lgn][maxn],mn[lgn+1][lgn][maxn],pwr[lgn+2];
vector<int> s,w;

void init(int _n,vector<int> _s,vector<int> p,vector<int> _w,vector<int> l){
	pwr[0]=1;
	for(int i=1;i<=lgn+1;++i)pwr[i]=pwr[i-1]*base;
	n=_n;s=_s;w=_w;
	for(int k=0;k<=lgn;++k){//win if <base^k, lose if >=base^k
		for(int i=0;i<n;++i){
			to[k][0][i]=(s[i]<pwr[k])?w[i]:l[i];
			gain[k][0][i]=(s[i]<pwr[k])?s[i]:p[i];
			mn[k][0][i]=(s[i]<pwr[k])?INF:s[i];
		}
		to[k][0][n]=n;
		gain[k][0][n]=0;
		mn[k][0][n]=INF;
		for(int j=1;j<lgn;++j){
			for(int i=0;i<=n;++i){
				int cur=i;
				mn[k][j][i]=INF;
				for(int b=0;b<base;++b){
					to[k][j][i]=to[k][j-1][cur];
					mn[k][j][i]=min(mn[k][j][i],mn[k][j-1][cur]-gain[k][j][i]);
					gain[k][j][i]+=gain[k][j-1][cur];
					cur=to[k][j-1][cur];
					if(cur==n)break;
				}
			}
		}
	}
}

ll simulate(int x,int z){
	ll str=z;
	int pos=x;
	while(pos!=n){
		int k=0;
		while(pwr[k+1]<=str)++k;
		if(k>lgn){
			int cur=pos;
			for(int b=0;b<base-1;++b){
				str+=gain[lgn][lgn-1][cur];
				cur=to[lgn][lgn-1][pos];
				if(cur==n)break;
			}
			return str;
		}
		for(int j=lgn-1;j>=0;--j){
			for(int b=0;b<base-1;++b){
				if(str<mn[k][j][pos]){
					str+=gain[k][j][pos];
					pos=to[k][j][pos];
				}
				else break;
			}
		}
		if(pos!=n){
			str+=s[pos];
			pos=w[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