Submission #782326

#	Time	Username	Problem	Language	Result	Execution time	Memory
782326		caganyanmaz	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	53 ms	37452 KiB

dungeons

#include <bits/stdc++.h>
#include "dungeons.h"

constexpr static int MXSIZE = 50001;
constexpr static int MXLOG = 25;
constexpr static int BIG = 1e9;
constexpr static int MXNUM = 1e7;

// Interval, step, current index
int blp[MXLOG][MXLOG][MXSIZE];
long long blc[MXLOG][MXLOG][MXSIZE];
int blm[MXLOG][MXLOG][MXSIZE]; // minimum needed for change
int reduce(long long a)
{
        if (a > MXNUM)
                return MXNUM;
        return a;
}

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l)
{
        for (int i = 0; i < MXLOG; i++)
        {
                // For numbers bigger than or equal to 1<<i but smaller than 1<<(i+1)
                for (int j = 0; j < n; j++)
                {
                        blp[i][0][j] = (s[j] <= (1<<i)) ? w[j] : l[j];
                        blc[i][0][j] = (s[j] <= (1<<i)) ? s[j] : p[j];
                        blm[i][0][j] = (s[j] <= (1<<i)) ? 1e9 : s[j];
                }
                blp[i][0][n] = n;
                blc[i][0][n] = 0;
                blm[i][0][n] = 0;
                for (int j = 1; j < n; j++)
                {
                        for (int k = 0; k <= n; k++)
                        {
                                blp[i][j][k] = blp[i][j-1][blp[i][j-1][k]];
                                blc[i][j][k] = blc[i][j-1][k] + blc[i][j-1][blp[i][j-1][k]];
                                blm[i][j][k] = std::min(blm[i][j-1][k], std::max(0, blm[i][j-1][blp[i][j-1][k]] - reduce(blc[i][j-1][k])));
                        }
                }
        }
}

long long simulate(int x, int z)
{
        for (int i = 31 - __builtin_clz(z); i < MXLOG; i++)
        {
                for (int j = MXLOG-1; j >= 0; j--)
                {
                        if (blm[i][j][x] > z)
                        {
                                z += blc[i][j][x];
                                x = blp[i][j][x];
                        }
                }
        }
        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