Submission #622846

#	Time	Username	Problem	Language	Result	Execution time	Memory
622846		Bench0310	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	5930 ms	486856 KiB

dungeons

#include <bits/stdc++.h>
#include "dungeons.h"
#pragma GCC target ("popcnt")

using namespace std;
typedef long long ll;

const int C=5; //cutoff between naive jumping and building base-4 jumps
const int N=400001;
int n;
int s[N];
int p[N];
int w[N];
int l[N];
int jump[N][11-C][12];
ll boost[N][11-C][12];
int mn[N][11-C][12];
int won[N];
int to[N];
int pw[N];
ll end_boost[N];
const int inf=(1<<30);
const int lim=10000000;

int msb(ll a)
{
    int b=63-__builtin_clzll(a);
    return (b/2);
}

void build(int lvl)
{
    for(int i=0;i<n;i++)
    {
        won[i]=(msb(s[i])<=lvl+C);
        to[i]=(won[i]==1?w[i]:l[i]);
        pw[i]=(won[i]==1?s[i]:p[i]);
    }
    won[n]=1; to[n]=n; pw[n]=0;
    //j=0
    for(int i=0;i<=n;i++)
    {
        jump[i][lvl][0]=to[i];
        boost[i][lvl][0]=pw[i];
        mn[i][lvl][0]=(won[i]==0?s[i]:inf);
    }
    //j>0
    for(int j=1;j<12;j++)
    {
        for(int i=0;i<=n;i++)
        {
            int a=i;
            ll b=0;
            int m=inf;
            for(int k=0;k<4;k++)
            {
                m=min(m,int(max(ll(0),mn[a][lvl][j-1]-b)));
                b+=boost[a][lvl][j-1];
                a=jump[a][lvl][j-1];
            }
            jump[i][lvl][j]=a;
            boost[i][lvl][j]=b;
            mn[i][lvl][j]=m;
        }
    }
}

void build_end()
{
    end_boost[n]=0;
    for(int i=n-1;i>=0;i--) end_boost[i]=s[i]+end_boost[w[i]];
}

void init(int tn,vector<int> ts,vector<int> tp,vector<int> tw,vector<int> tl)
{
    n=tn;
    for(int i=0;i<n;i++){s[i]=ts[i]; p[i]=tp[i]; w[i]=tw[i]; l[i]=tl[i];}
    for(int i=0;i<=10-C;i++) build(i);
    build_end();
}

ll simulate(int a,int z)
{
    ll b=z;
    auto mv=[&]()
    {
        if(b>=s[a])
        {
            b+=s[a];
            a=w[a];
        }
        else
        {
            b+=p[a];
            a=l[a];
        }
    };
    while(b<=(1<<(2*(C+1)))-1)
    {
        mv();
        if(a==n) return b;
    }
    while(a!=n)
    {
        int lvl=min(msb(b)-1,11)-C;
        if(lvl==11-C) break;
        while(a!=n&&min(msb(b)-1,11)-C==lvl)
        {
            for(int j=11;j>=0;j--)
            {
                for(int k=0;k<3;k++)
                {
                    if(jump[a][lvl][j]!=n&&b<mn[a][lvl][j])
                    {
                        b+=boost[a][lvl][j];
                        a=jump[a][lvl][j];
                    }
                }
            }
            mv();
        }
    }
    b+=end_boost[a];
    return b;
}

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