Submission #538997

#	Time	Username	Problem	Language	Result	Execution time	Memory
538997		79brue	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	4313 ms	1561244 KiB

dungeons

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

using namespace std;

typedef long long ll;
const int LIM = 25;

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

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

int idxArr[30];
inline int idx(int A, int B){
    return idxArr[A] + B;
}

void init(int N, vector<int> s, vector<int> p, vector<int> W, vector<int> L){
    for(int i=1; i<=26; i++) idxArr[i] = idxArr[i-1] + i;

	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] = 1e9, power[n]=1e9;

    for(int f=0; f<LIM; f++){
        for(int i=0; i<=n; i++){
            int tmp = idx(f,0);
            if((1<<f) <= arr[i]){
                nxt[tmp][i] = l[i];
                sum[tmp][i] = power[i];
                lim[tmp][i] = arr[i]-1;
            }
            else{
                nxt[tmp][i] = w[i];
                sum[tmp][i] = arr[i];
                lim[tmp][i] = 1e9;
            }
        }
        for(int d=1; d<=f; d++){
            for(int i=0; i<=n; i++){
                int tmp = idx(f,d);
                nxt[tmp][i] = nxt[tmp-1][nxt[tmp-1][i]];
                sum[tmp][i] = min(1000000000, sum[tmp-1][i] + sum[tmp-1][nxt[tmp-1][i]]);
                lim[tmp][i] = min(lim[tmp-1][i], lim[tmp-1][nxt[tmp-1][i]] - sum[tmp-1][i]);
            }
        }
    }

    for(int i=n-1; i>=0; i--){
        bonus[i] = ll(arr[i]) + bonus[w[i]];
    }
}

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

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

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

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

        if(x==n) break;

        assert(z < (1<<(f+1)));
        if(z >= arr[x]) z += arr[x], x = w[x];
        else z += power[x], x = l[x];
        assert(z >= (1<<(f+1)));
    }

    return ll(z) + bonus[x];
}

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