Submission #457617

#	Time	Username	Problem	Language	Result	Execution time	Memory
457617		blue	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	8 ms	6260 KiB

dungeons

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

const int maxN = 50'000;
const int lgN = 20;
const int lgS = 25;
//
int N;
vector<int> S;
vector<int> P;
vector<int> W;
vector<int> L;
//
int nxt[maxN + 1][lgS][lgN]; //dungeon
long long gain[maxN + 1][lgS][lgN];

//magnitude(s) == k <=> 2^k <= s < 2^(k+1)

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l)
{
    s.push_back(0);
    p.push_back(0);
    w.push_back(n);
    l.push_back(n);

    N = n;
    S = s;
    P = p;
    W = w;
    L = l;

    for(int i = 0; i <= N; i++)
    {
        for(int k = 0; k < lgS; k++)
        {
            if(s[i] < (1 << k))
            {
                nxt[i][k][0] = w[i];
                gain[i][k][0] = s[i];
            }
            else
            {
                nxt[i][k][0] = l[i];
                gain[i][k][0] = p[i];
            }
        }
    }

    for(int e = 1; e < lgN; e++)
    {
        for(int i = 0; i <= N; i++)
        {
            for(int k = 0; k < lgS; k++)
            {
                nxt[i][k][e] = nxt[ nxt[i][k][e-1] ][k][e-1];
                gain[i][k][e] = gain[i][k][e-1] + gain[ nxt[i][k][e-1] ][k][e-1];
            }
        }
    }
}

long long simulate(int x, int z)
{
    // cerr << "simulate " << x << ' ' << z << '\n';
    int X = x;
    long long Z = z;

    for(int k = 0; k < lgS; k++)
    {
        // cerr << "k = " << k << '\n';
        if((1 << (k+1)) <= Z)
            continue;

        for(int e = lgN - 1; e >= 0; e--)
        {
            // cerr << "e = " << e << ", nxt = " << nxt[X][k][e] << '\n';
            if(Z + gain[X][k][e] >= (1 << (k+1))) continue;
            Z += gain[X][k][e];
            X = nxt[X][k][e];
        }

        if(Z >= S[X])
        {
            Z += S[X];
            X = W[X];
        }
        else
        {
            Z += P[X];
            X = L[X];
        }
    }
    // cerr << "X = " << X << '\n';
    // cerr << "N = " << N << '\n';
    return Z;
}

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