Submission #542916

#	Time	Username	Problem	Language	Result	Execution time	Memory
542916		alextodoran	Dungeons Game (IOI21_dungeons)	C++17	24 / 100	7057 ms	649584 KiB

dungeons

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 50000;
const int N_QITS = 22;
const int S_BITS = 25;

int N;
int strength[N_MAX];
int winBonus[N_MAX];
int loseBonus[N_MAX];
int winEdge[N_MAX];
int loseEdge[N_MAX];

struct Jump {
    int last;
    ll bonus;
    ll maxDiff;
    // maximum (bonus - strength) at some moment when we lost
};
Jump operator + (const Jump &j1, const Jump &j2) {
    return Jump{j2.last, j1.bonus + j2.bonus, max(j1.maxDiff, j1.bonus + j2.maxDiff)};
}

Jump jump[N_MAX + 1][S_BITS][N_QITS];

void init (int _N, vector <int> _S, vector <int> _P, vector <int> _W, vector <int> _L) {
    // Transfer input to global
    N = _N;
    for (int u = 0; u < N; u++) {
        strength[u] = _S[u];
        winBonus[u] = _S[u];
        loseBonus[u] = _P[u];
        winEdge[u] = _W[u];
        loseEdge[u] = _L[u];
    }
    // Precompute jumps
    for (int sbit = 0; sbit < S_BITS; sbit++) {
        for (int nqit = 0; nqit < N_QITS; nqit++) {
            jump[N][sbit][nqit] = Jump{N, 0, LLONG_MIN};
        }
    }
    for (int u = 0; u < N; u++) {
        for (int sbit = 0; sbit < S_BITS; sbit++) {
            if ((1 << sbit) > strength[u]) {
                jump[u][sbit][0] = Jump{winEdge[u], winBonus[u], LLONG_MIN};
            } else {
                jump[u][sbit][0] = Jump{loseEdge[u], loseBonus[u], 0 - strength[u]};
            }
        }
    }
    for (int nqit = 1; nqit < N_QITS; nqit++) {
        for (int u = 0; u < N; u++) {
            for (int sbit = 0; sbit < S_BITS; sbit++) {
                Jump j = jump[u][sbit][nqit - 1];
                j = j + jump[j.last][sbit][nqit - 1];
                j = j + jump[j.last][sbit][nqit - 1];
                j = j + jump[j.last][sbit][nqit - 1];
                jump[u][sbit][nqit] = j;
            }
        }
    }
}

ll simulate (int u, int initStrength) {
    ll currStrength = initStrength;
    while (true) {
        for (int nqit = N_QITS - 1; nqit >= 0; nqit--) {
            int sbit = (currStrength < (1 << S_BITS) ? 31 - __builtin_clz(currStrength) : S_BITS - 1);
            Jump j = jump[u][sbit][nqit];
            while (u < N && currStrength + j.maxDiff < 0) {
                u = j.last;
                currStrength += j.bonus;
                j = jump[u][sbit][nqit];
            }
        }
        if (u == N) {
            break;
        }
        if (currStrength >= strength[u]) {
            currStrength += winBonus[u];
            u = winEdge[u];
        } else {
            currStrength += loseBonus[u];
            u = loseEdge[u];
        }
    }
    return currStrength;
}

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