Submission #1117477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117477		welleyth	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3040 ms	2072136 KiB

dungeons

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

constexpr int N = (int)4e5+1;
constexpr int K = 20;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

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

int norm(long long x){
    if(x > (int)2e9) return (int)2e9;
    else return x;
}

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);
            maxPref[id][0][i] = (val < s[i] ? -s[i] : -(int)2e9);
        }
        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] = norm((long long)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]];
                maxPref[id][j][i] = norm(max((long long)maxPref[id][j-1][i], (long long)sum[id][j-1][i] + maxPref[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(!win[id][i][pos] && power + maxPref[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];
}

Compilation message (stderr)

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:72:19: warning: unused variable 'goal' [-Wunused-variable]
   72 |         long long goal = (1 << (id + 1));
      |                   ^~~~

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