제출 #1133810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133810		Szymon_Pilipczuk	던전 (IOI21_dungeons)	C++20	13 / 100	1319 ms	187988 KiB

dungeons

#include <bits/stdc++.h>
#include "dungeons.h"
using namespace std;
long long j[13][12][400001][3];
int pot[13];
long long inf;
int n;
int s[400001];
int p[400001];
int w[400001];
int l[400001];
int g[10000001];
int k = 12;
int blog = 4;
vector<long long> t;
void init(int nt,vector<int> st,vector<int> pt,vector<int> wt,vector<int> lt)
{
    inf = 1e18;
    pot[0] = 1;
    for(int i = 1;i<=k;i++)
    {
        pot[i] = pot[i-1]*blog;
    }
    n = nt;
    for(int i =0 ;i<n;i++)
    {
        s[i] = st[i];
        p[i] = pt[i];
        w[i] = wt[i];
        l[i] = lt[i];
    }
    s[n] = 0;
    p[n] = 0;
    w[n] = n;
    l[n] = n;
    for(int i = 0;i<=k;i++)
    {
        for(int q = 0;q<n;q++)
        {
            if(s[q] < pot[i])
            {
                j[i][0][q][0] = w[q];
                j[i][0][q][1] = inf;
                j[i][0][q][2] = s[q];
            }
            else
            {
                j[i][0][q][0] = l[q];
                j[i][0][q][1] = s[q];
                j[i][0][q][2] = p[q];
            }
        }
        j[i][0][n][0] = n;
        j[i][0][n][1] = inf;
        j[i][0][n][2] = 0;
    }
    for(int i = 0;i<=k;i++)
    {
        for(int w = 1;w<k;w++)
        {
            for(int q= 0;q<=n;q++)
            {
                j[i][w][q][0] = j[i][w-1][j[i][w-1][j[i][w-1][j[i][w-1][q][0]][0]][0]][0];
                j[i][w][q][1] = min(min(j[i][w-1][q][1],j[i][w-1][j[i][w-1][q][0]][1]-j[i][w-1][q][2]),min(j[i][w-1][j[i][w-1][j[i][w-1][q][0]][0]][1]-j[i][w-1][j[i][w-1][q][0]][2]-j[i][w-1][q][2],j[i][w-1][j[i][w-1][j[i][w-1][j[i][w-1][q][0]][0]][0]][1]-j[i][w-1][j[i][w-1][j[i][w-1][q][0]][0]][2]-j[i][w-1][j[i][w-1][q][0]][2]-j[i][w-1][q][2]));
                j[i][w][q][2] = j[i][w-1][q][2] + j[i][w-1][j[i][w-1][q][0]][2] + j[i][w-1][j[i][w-1][j[i][w-1][q][0]][0]][2] +j[i][w-1][j[i][w-1][j[i][w-1][j[i][w-1][q][0]][0]][0]][2];
                /*if(i == 4 && q == 1)
                {
                    cerr<<j[i][w][q][1]<<"\n";
                    cerr<<j[i][w-1][q][2]<<" "<<j[i][w-1][j[i][w-1][q][0]][1]<<"\n";
                }*/
            }
        }
    }
    /*for(int i = 0;i<k;i++)
    {
        for(int w = 0;w<k;w++)
        {
            for(int q =0;q<=n;q++)
            {
                cerr<<j[i][w][q][0]<<" "<<j[i][w][q][1]<<" "<<j[i][w][q][2]<<"\n";
            }
            cerr<<"\n";
        }
        cerr<<"\n";
    }*/
}
long long simulate(int x,int zt)
{
    long long z = zt;
    for(int i = 0;i<k;i++)
    {
        for(int w = k-1;w>=0;w--)
        {
            for(int r = 0;r<blog-1;r++)
            {
                if(j[i][w][x][1] > z && j[i][w][x][2]+z < pot[i+1])
                {
                    z += j[i][w][x][2];
                    x = j[i][w][x][0];
                }
                /*if(i == 4 && r == 1)
                {
                    cerr<<x<<" "<<z<<"\n";
                    if(w == 11)
                    {
                        cerr<<j[i][w][x][1]<<"\n";
                    }
                }*/
            }
        }

        if(z < pot[i+1])
        {
            if(z < s[x])
            {
                z+= p[x];
                x = l[x];
            }
            else
            {
                z+=s[x];
                x = w[x];
            }
        }
        //cerr<<i<<" "<<pot[i]<<" "<<z<<" "<<x<<"\n";

        //cerr<<"\n";

    }
    z += j[k][11][x][2];
    //cerr<<"\n";
    return z;
}

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