Submission #832677

#	Time	Username	Problem	Language	Result	Execution time	Memory
832677		welleyth	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	7038 ms	543984 KiB

dungeons

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

constexpr int N = (int)5e4+1;
constexpr int K = (int)21;

int s[N],p[N],w[N],l[N];
int n;
long long go[K][K][N];
long long sum[K][K][N];
long long goWin[N];
bool win[K][K][N];
long long minPref[K][K][N];
vector<int> SValues;

void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
    n = _n;
    for(int i = 0; i < n; i++){
        s[i] = _s[i];
        p[i] = _p[i];
        w[i] = _w[i];
        l[i] = _l[i];
        SValues.push_back(s[i]);
    }
    SValues.push_back(0);
    sort(SValues.begin(),SValues.end());
    SValues.erase(unique(SValues.begin(),SValues.end()),SValues.end());
    int id = 0;
    for(int _t = 0; _t < K; _t++){
        int val = (1 << _t);
        id = _t;
        for(int i = 0; i < n; i++){
            int to = (val < s[i] ? l[i] : w[i]);
            int add = (val < s[i] ? p[i] : s[i]);
            go[id][0][i] = to;
            sum[id][0][i] = add;
            win[id][0][i] = (to == n);
            minPref[id][0][i] = -s[i];
            // if(l[i] == n) sumLose[0][i] = (int)1e9;
        }
        for(int j = 1; j < K; j++){
            for(int i = 0; i < n; i++){
                go[id][j][i] = go[id][j-1][go[id][j-1][i]];
                sum[id][j][i] = sum[id][j-1][i] + sum[id][j-1][go[id][j-1][i]];
                win[id][j][i] = win[id][j-1][i] || win[id][j-1][go[id][j-1][i]];
                minPref[id][j][i] = min(minPref[id][j-1][i], sum[id][j-1][i] + minPref[id][j-1][go[id][j-1][i]]);
            }
        }
        id++;
    }
    for(int i = n-1; i >= 0; i--){
        goWin[i] = goWin[w[i]] + s[i];
    }
    return;
}

long long simulate(int _x, int _z) {
    int pos = _x;
    long long power = _z;
    while(power < SValues.back()){
        int id = 0;
        for(int i = 0; i < K; i++) if(power >> i & 1) id = i;
        long long goal = (1 << (id + 1));
        for(int i = K-1; i >= 0; i--){
            if(power + sum[id][i][pos] < goal && !win[id][i][pos] && power + minPref[id][i][pos] >= 0){
                power += sum[id][i][pos];
                pos = go[id][i][pos];
            }
        }
        if(pos == n)
            return power;
        int to = (power < s[pos] ? l[pos] : w[pos]);
        int add = (power < s[pos] ? p[pos] : s[pos]);            
        power += add;
        pos = to;
        if(pos == n)
            return power;
    }
    
    return power + goWin[pos];
}

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