Submission #439959

#	Time	Username	Problem	Language	Result	Execution time	Memory
439959		dacin21	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3531 ms	294028 KiB

dungeons

#undef _GLIBCXX_DEBUG

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

using ll = int64_t;

const int BLOCK_1 = 500;
const int BLOCK_2 = 50000;
const int MAX_SKILL = 1.01e7;
const int U = 20;
const int inf = 1e9;

int n;
struct Link{
    int to;
    int gain;
};
struct Node{
    Link win, loss;
    int thresh;
};
struct Jump{
    int to;
    int max_valid;
    ll gain;
};
vector<ll> win_gain;
vector<Node> g;
vector<vector<Jump> > jumps_1;
vector<vector<Jump> > jumps_2;

void init(int n_, vector<int> s, vector<int> p, vector<int> w, vector<int> l){
	n = n_;
	g.assign(n+1, Node{});
	for(int i=0; i<n; ++i){
        g[i] = Node{Link{w[i], s[i]}, Link{l[i], p[i]}, s[i]};
	}
	g[n] = Node{Link{n, 0}, Link{n, 0}, 0};

	// compute win once we hit 1e7
	win_gain.assign(n+1, 0);
	for(int i=n-1; i>=0; --i){
        win_gain[i] = win_gain[g[i].win.to] + g[i].win.gain;
	}

	auto compute_table = [&](auto &jumps, int BLOCK){
        // assume we take BLOCK steps
        // then build jump table
        jumps.resize(U+1, vector<Jump>(n+1));
        for(int i=0; i<=n; ++i){
            if(g[i].thresh <= BLOCK){
                jumps[0][i] = Jump{g[i].win.to, inf, g[i].win.gain};
            } else {
                jumps[0][i] = Jump{g[i].loss.to, g[i].thresh-1, g[i].loss.gain};
            }
        }
        jumps[0][n].max_valid = 0;
        for(int i=1; i<=U; ++i){
            for(int j=0; j<=n; ++j){
                auto &e = jumps[i-1][j];
                const int k = e.to;
                auto const&f = jumps[i-1][k];
                jumps[i][j] = Jump{f.to, max<ll>(-1, min<ll>(e.max_valid, f.max_valid-e.gain)), e.gain+f.gain};
            }
        }
	};
	compute_table(jumps_1, BLOCK_1);
	compute_table(jumps_2, BLOCK_2);
}

long long simulate(int x, int z) {
    int u = x;
    ll s = z;
    auto do_single_step = [&](){
        if(s >= g[u].thresh){
            s += g[u].win.gain;
            u = g[u].win.to;
        } else {
            s += g[u].loss.gain;
            u = g[u].loss.to;
        }
    };
    auto run_with_jumps = [&](auto const&jumps, int const SKILL_CAP){
        while(u != n && s < SKILL_CAP){
            int i = 0;
            while(i >= 0){
                auto &e = jumps[i][u];
                if(s < e.max_valid){
                    s += e.gain;
                    u = e.to;
                    i = min(i+1, U);
                } else --i;
            }
            do_single_step();
        }
    };
    for(int it=0; it<BLOCK_1; ++it){
        do_single_step();
    }
    assert(u == n || s >= BLOCK_1);
    run_with_jumps(jumps_1, BLOCK_2);
    run_with_jumps(jumps_2, MAX_SKILL);
    s += win_gain[u];
    return s;
}

Compilation message (stderr)

dungeons.cpp: In instantiation of 'init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(auto:23&, int)> [with auto:23 = std::vector<std::vector<Jump> >]':
dungeons.cpp:69:32:   required from here
dungeons.cpp:65:29: warning: narrowing conversion of '(long int)std::max<long int>(-1, (* & std::min<long int>(((long int)e.Jump::max_valid), (((ll)((int)f.Jump::max_valid)) - e.Jump::gain))))' from 'long int' to 'int' [-Wnarrowing]
   65 |                 jumps[i][j] = Jump{f.to, max<ll>(-1, min<ll>(e.max_valid, f.max_valid-e.gain)), e.gain+f.gain};
      |                 ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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