제출 #1229241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229241		Malix	던전 (IOI21_dungeons)	C++17	11 / 100	7160 ms	2136672 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int X,Y,n;
vector<vii> ps;
vector<vector<vector<ll>>> sm,th;
vi W,L;
vector<ll> s,p,pw;

void init(int N, std::vector<int> arr, std::vector<int> P, std::vector<int> w, std::vector<int> l) {
	X=10;n=N;
	W=w;L=l;
	s.resize(n);p.resize(n);
	REP(i,0,n)s[i]=(ll)arr[i];
	REP(i,0,n)p[i]=(ll)P[i];
	Y=log2(n)+2;
	pw.resize(X+1,1);
	REP(i,1,X+1)pw[i]=pw[i-1]*8LL;
	ps.resize(X,vii(n,vi(Y)));
	sm.resize(X,vector<vector<ll>>(n,vector<ll>(Y)));
	th.resize(X,vector<vector<ll>>(n,vector<ll>(Y)));
	REP(i,0,X){
		REP(j,0,n){
			if(s[j]<pw[i]){
				ps[i][j][0]=w[j];
				sm[i][j][0]=s[j];
			}
			else{
				ps[i][j][0]=l[j];
				sm[i][j][0]=p[j];
			}
			if(i!=X-1)th[i][j][0]=s[j];
			else th[i][j][0]=INF;
		}
		REP(k,1,Y)REP(j,0,n){
			if(ps[i][j][k-1]==n){
				ps[i][j][k]=n;
				continue;
			}
			ps[i][j][k]=ps[i][ps[i][j][k-1]][k-1];
			sm[i][j][k]=sm[i][j][k-1]+sm[i][ps[i][j][k-1]][k-1];
			th[i][j][k]=min(th[i][j][k-1],th[i][ps[i][j][k-1]][k-1]-sm[i][j][k-1]);
		}
	}
	return;
}

long long simulate(int x, int z) {
	ll y=(ll)z;
	while(x!=n){
		int t=upper_bound(all(pw),y)-pw.begin();
		t--;
		t=min(t,9);
		for(int k=Y-1;k>=0;k--)if(ps[t][x][k]!=n&&y<th[t][x][k]){
			y+=sm[t][x][k];
			x=ps[t][x][k];
		}
		if(s[x]<=y){
			y+=s[x];
			x=W[x];
		}
		else{
			y+=p[x];
			x=L[x];
		}
	}
	return y;
}

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