Submission #623424

#	Time	Username	Problem	Language	Result	Execution time	Memory
623424		tinjyu	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	4786 ms	1397932 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <iostream>
using namespace std;
int cnt=0;
 
int n,s[1000005],p[1000005],l[1000005],w[1000005];
 
int step[400005][7][25];
long long int d[400005][7][25];
long long int mx[400005][7][25];
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<5;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<24;len++)
        {
            for(int i=0;i<n;i++)
            {
                long long int ti=2,now=i;
                mx[i][bits][len]=1e18;
                while(ti--)
                {
                    if(now==n)break;
                    mx[i][bits][len]=min(mx[i][bits][len],mx[now][bits][len-1]-d[i][bits][len]);
                    d[i][bits][len]+=d[now][bits][len-1];
                    step[i][bits][len]=step[now][bits][len-1];
                    now=step[i][bits][len];
                }
            }
        }
        b*=64;
    }
    return;
}
 
long long simulate(int x,int Z) {
    //cnt++;
    //if(cnt%1000==0)cout<<x<<" "<<Z<<endl;
    int now=x;
    long long int z=Z;
    long long int b=1;
    for(int bits=0;bits<5;bits++)
    {
        if(bits!=4 && b*64<=z)
        {
            b*=64;
            continue;
        }
        for(int len=23;len>=0;len--)
        {
            long long int count=0;
            
            while(z<mx[now][bits][len])
            {
                count++;
                //cout<<b<<" "<<bits<<" "<<now<<" "<<z<<" "<<mx[now][bits][len]<<" "<<len<<" "<<count<<" "<<s[now]<<" "<<p[now]<<" "<<w[now]<<" "<<l[now]<<endl;
                z+=d[now][bits][len];
                now=step[now][bits][len];
                //cout<<b<<" "<<bits<<" "<<now<<" "<<z<<" "<<mx[now][bits][len]<<" "<<len<<" "<<count<<" "<<s[now]<<" "<<p[now]<<" "<<w[now]<<" "<<l[now]<<endl;
                if(now==n)break;
            }
            if(now==n)break;
        }
        if(now==n)break;
        z+=s[now];
        now=w[now];
        if(now==n)break;
        //cout<<now<<" "<<z<<endl;
        b*=64;
        if(z<b)
        {
            b/=64;
            bits--;
        }
    }
    //system("pause");
	return z;
}

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