Submission #782378

#	Time	Username	Problem	Language	Result	Execution time	Memory
782378		caganyanmaz	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	1248 ms	1016928 KiB

dungeons

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

void __print(int i) { std::cerr << i; }
void __print(const char *c) {std::cerr << c; }
void __print(long long i) { std::cerr << i; }

template<typename T>
void __print(const T& t) { std::cerr << "{"; int f = 0; for (const auto& i : t) { std::cerr << (f++ ? ", " : ""); __print(i); } std::cerr << "}"; }

void _print() { std::cerr << "]\n"; }
template<typename T, typename... V>
void _print(T t, V... v) { __print(t); if (sizeof...(v)) std::cerr << ", "; _print(v...); }
#ifdef DEBUGGING
#define debug(x...) std::cerr << "[" << (#x) << "] = ["; _print(x)
#else
#define debug(x...)
#endif

constexpr static int MXSIZE = 50001;
constexpr static int MXLOG = 25;
constexpr static long long INF = 1e18;
constexpr static int BIG = 1e8;
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
std::vector<int> s, w, p, l;
int n;
int sub(int a, long long b)
{
        if (b > a)
                return 0;
        return a - b;
}

void init(int nn, std::vector<int> ss, std::vector<int> pp, std::vector<int> ww, std::vector<int> ll)
{
        n = nn;
        s = ss;
        w = ww;
        p = pp;
        l = ll;
        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++)
                {
                        if (s[j] <= (1<<i))
                        {
                                blp[i][0][j] = w[j];
                                blc[i][0][j] = s[j];
                                blm[i][0][j] = BIG;
                        }
                        else
                        {
                                blp[i][0][j] = l[j];
                                blc[i][0][j] = p[j];
                                blm[i][0][j] = s[j];
                        }
                }
                blp[i][0][n] = n;
                blc[i][0][n] = 0;
                blm[i][0][n] = 0;
                for (int j = 1; j < MXLOG; j++)
                {
                        for (int k = 0; k <= n; k++)
                        {
                                int nxt = blp[i][j-1][k];
                                blp[i][j][k] = blp[i][j-1][nxt];
                                blc[i][j][k] = blc[i][j-1][k] + blc[i][j-1][nxt];
                                blm[i][j][k] = std::min(blm[i][j-1][k], sub(blm[i][j-1][nxt], blc[i][j-1][k]));
                        }
                }
        }
}

long long simulate(int x, int zz)
{
        long long z = zz;
        debug(x);
        for (int i = 0; i < MXLOG; i++)
        {
                debug(i, x, z);
                for (int j = MXLOG-1; j >= 0; j--)
                {
                        if (blm[i][j][x] == BIG || static_cast<long long>(blm[i][j][x]) > z)
                        {
                                z += blc[i][j][x];
                                x = blp[i][j][x];
                        }
                }
                if (x < n && z >= s[x])
                {
                        z += s[x];
                        x = w[x];
                }
                else if (x < n)
                {
                        z += p[x];
                        x = l[x];
                }
        }
        debug(x, n);
        assert(x == n);
        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