Submission #794133

#	Time	Username	Problem	Language	Result	Execution time	Memory
794133		finn__	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	2139 ms	736512 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

constexpr size_t N = 50001, B = 100, S = 10000000, K = 25; // B: number of blocks

size_t n;
uint16_t f[K][N][B];
uint32_t u[K][N][B]; // sum of strength gained
uint32_t block_begin[B + 1];
bitset<B> completed[N];
vector<int> s, p, w, l;

template <typename T, T MAX>
T saturating_add(T a, T b)
{
    return MAX - a < b ? MAX : a + b;
}

size_t state_lca(size_t i, size_t j1, size_t j2)
{
    for (size_t k = 0; k < K; ++k)
        if (f[k][i][j1] != f[k][i][j2] || u[k][i][j1] != u[k][i][j2])
            return k;
}

size_t get_block(size_t i)
{
    size_t a = 0, len = B;
    while (len > 1)
    {
        len >>= 1;
        a += (block_begin[a + len] <= i) ? len : 0;
    }
    return a;
}

void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_)
{
    if (n > 50000)
        return;
    n = n_;
    s = move(s_);
    p = move(p_);
    w = move(w_);
    l = move(l_);

    for (size_t i = 0; i <= B; ++i)
        block_begin[i] = (i * S) / B;

    for (size_t i = 0; i < n; ++i)
    {
        for (size_t j = 0; j < B; ++j)
        {
            if (block_begin[j + 1] <= s[i])
                f[0][i][j] = l[i], u[0][i][j] = p[i];
            else if (block_begin[j] > s[i])
                f[0][i][j] = w[i], u[0][i][j] = s[i];
            else
                f[0][i][j] = i, completed[i] = 1;
        }
    }

    for (size_t k = 1; k < K; ++k)
    {
        for (size_t i = 0; i < n; ++i)
        {
            for (size_t j = 0; j < B; ++j)
            {
                if (!completed[i][j])
                {
                    uint64_t const x = get_block(block_begin[j] + u[k - 1][i][j]),
                                   y = get_block(block_begin[j + 1] - 1 + u[k - 1][i][j]);
                    size_t const intermediate = f[k - 1][i][j];
                    if (f[k - 1][intermediate][x] == f[k - 1][intermediate][y] &&
                        u[k - 1][intermediate][x] == u[k - 1][intermediate][y])
                    {
                        f[k][i][j] = f[k - 1][intermediate][x];
                        u[k][i][j] = saturating_add<uint32_t, S>(u[k - 1][i][j], u[k - 1][intermediate][x]);
                    }
                    else
                    {
                        assert(y == x + 1);
                        size_t const l = state_lca(intermediate, x, y);
                        if (!l)
                        {
                            f[k][i][j] = intermediate;
                            u[k][i][j] = u[k - 1][i][j];
                            completed[i][j] = 1;
                        }
                        else
                        {
                            f[k][i][j] = f[l - 1][intermediate][x];
                            u[k][i][j] = saturating_add<uint32_t, S>(u[k - 1][i][j], u[l - 1][intermediate][x]);
                            completed[i][j] = 1;
                        }
                    }
                }
                else
                {
                    f[k][i][j] = f[k - 1][i][j];
                    u[k][i][j] = u[k - 1][i][j];
                }
            }
        }
    }
}

long long simulate(int x, int z)
{
    if (!n)
        return 0;
    size_t i = x;
    uint64_t strength = z;
    while (i != n)
    {
        size_t block = get_block(strength);
        size_t j = f[K - 1][i][block];
        strength += u[K - 1][i][block];
        if (strength >= s[j])
        {
            i = w[j];
            strength += s[j];
        }
        else
        {
            i = l[j];
            strength += p[j];
        }
    }
    return strength;
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:55:36: warning: comparison of integer expressions of different signedness: 'uint32_t' {aka 'unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   55 |             if (block_begin[j + 1] <= s[i])
dungeons.cpp:57:37: warning: comparison of integer expressions of different signedness: 'uint32_t' {aka 'unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   57 |             else if (block_begin[j] > s[i])
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:120:22: warning: comparison of integer expressions of different signedness: 'uint64_t' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
  120 |         if (strength >= s[j])
dungeons.cpp: In function 'size_t state_lca(size_t, size_t, size_t)':
dungeons.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
   25 | }
      | ^

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