제출 #531601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531601		79brue	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	19 ms	30400 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
ll arr[400002], power[400002];
int w[400002], l[400002];

ll nxt[25][50002][25]; /// 계속 지기만 했을 때의 최종 위치
ll sum[25][50002][25]; /// 계속 지기만 했을 때의 체력 변화
ll lim[25][50002][25]; /// 계속 지기만 할 수 있기 위한 최초 체력의 최댓값

void init(int N, vector<int> s, vector<int> p, vector<int> W, vector<int> L){
	n = N;
	for(int i=0; i<n; i++) arr[i] = s[i];
	for(int i=0; i<n; i++) power[i] = p[i], w[i]=W[i], l[i]=L[i];
	l[n]=w[n]=n;
	arr[n] = 1e18, power[n]=0;

    for(int f=0; f<25; f++){
        for(int i=0; i<=n; i++) nxt[f][i][0] = l[i], sum[f][i][0] = power[i], lim[f][i][0] = arr[i]-1;
        for(int d=1; d<25; d++){
            for(int i=0; i<=n; i++){
                nxt[f][i][d] = nxt[f][nxt[f][i][d-1]][d-1];
                sum[f][i][d] = sum[f][i][d-1] + sum[f][nxt[f][i][d-1]][d-1];
                lim[f][i][d] = min(lim[f][i][d-1], lim[f][nxt[f][i][d-1]][d-1] - sum[f][i][d-1]);
            }
        }
    }
}

ll simulate(int x, int z){
    for(int f=0; f<25; f++){
        if((1<<(f+1)) <= z) continue;

        /// 1. 계속 지다가 결국 탈출하기
        int minLeft = (1<<(f+1)) - z;
        ll pSum = 0;
        int tx = x, cnt1 = 0;
        for(int d=24; d>=0; d--){
            if(pSum + sum[f][tx][d] < minLeft){
                pSum += sum[f][tx][d];
                tx = nxt[f][tx][d];
                cnt1 += (1<<d);
            }
        }

        /// 2. 이겨서 탈출하기
        int cnt2 = 0;
        tx = x;
        int tz = z;
        for(int d=24; d>=0; d--){
            if(lim[f][tx][d] >= tz){
                tz += sum[f][tx][d];
                tx = nxt[f][tx][d];
                cnt2 += (1<<d);
            }
        }

        int cnt = min(cnt1, cnt2);
        for(int d=0; d<25; d++){
            if((cnt>>d)&1){
                z += sum[f][x][d];
                x = nxt[f][x][d];
            }
        }

        if(z >= arr[x]) z += arr[x], x = w[x];
        else z += power[x], x = l[x];
    }
    return z;
}

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