제출 #832682

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832682		welleyth	던전 (IOI21_dungeons)	C++17	63 / 100	2131 ms	832628 KiB

dungeons

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

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

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

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 maxPref[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);
            maxPref[id][0][i] = (val < s[i] ? -s[i] : -(long long)1e10);
            // 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]];
                maxPref[id][j][i] = max(maxPref[id][j-1][i], 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];
}

컴파일 시 표준 에러 (stderr) 메시지

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

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