Submission #623342

#	Time	Username	Problem	Language	Result	Execution time	Memory
623342		tinjyu	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	7028 ms	240624 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <iostream>
using namespace std;

long long int n,s[1000005],p[1000005],l[1000005],w[1000005];

long long int step[400005][25][8];
long long int d[400005][25][8];
long long int mx[400005][25][8];
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
	n=N;
    for(int i=0;i<n;i++)s[i]=S[i];
    for(int i=0;i<n;i++)p[i]=P[i];
    for(int i=0;i<n;i++)w[i]=W[i];
    for(int i=0;i<n;i++)l[i]=L[i];

    long long int b=1;
    for(int bits=0;bits<25;bits++)
    {
        for(int i=0;i<n;i++)
        {
            if(s[i]>b)
            {
                step[i][bits][0]=l[i];
                mx[i][bits][0]=s[i];
                d[i][bits][0]=p[i];
            }
            else 
            {
                step[i][bits][0]=W[i];
                mx[i][bits][0]=1e18;
                d[i][bits][0]=S[i];
            }
        }
        for(int len=1;len<8;len++)
        {
            for(int i=0;i<n;i++)
            {
                long long int ti=8,now=i;
                while(ti--)
                {
                    if(now==n)break;
                    mx[i][bits][len]=min(mx[i][bits][len],mx[now][bits][len-1]-d[i][bits][len-1]);
                    d[i][bits][len]+=d[now][bits][len-1];
                    step[i][bits][len]=step[now][bits][len-1];
                    now=step[i][bits][len];
                }
            }
        }
        b*=2;
    }
    return;
}

long long simulate(int x, int z) {
    long long int now=x;
    long long int b=1;
    for(int bits=0;bits<25;bits++)
    {
        if(b*2<=z)
        {
            b*=2;
            continue;
        }
        for(int len=7;len>=0;len--)
        {
            while(z<mx[now][bits][len])
            {
                z+=d[now][bits][len];
                now=step[now][bits][len];
                if(now==n)break;
            }
        }
        if(now==n)break;
        z+=s[now];
        now=w[now];
        b*=2;
    }
	return z;
}

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