oj.uz

Submission #832682

# Submission time Handle Problem Language Result Execution time Memory
832682 2023-08-21T13:43:58 Z welleyth Dungeons Game (IOI21_dungeons) C++17
63 / 100
 2131 ms 832628 KB 
#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];
}

Compilation message

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12628 KB Output is correct
2 Correct 5 ms 12884 KB Output is correct
3 Correct 20 ms 45760 KB Output is correct
4 Correct 482 ms 830060 KB Output is correct
5 Correct 30 ms 45792 KB Output is correct
6 Correct 391 ms 830080 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29268 KB Output is correct
2 Runtime error 123 ms 14768 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29268 KB Output is correct
2 Correct 433 ms 830912 KB Output is correct
3 Correct 418 ms 830860 KB Output is correct
4 Correct 387 ms 830912 KB Output is correct
5 Correct 389 ms 830956 KB Output is correct
6 Correct 505 ms 830912 KB Output is correct
7 Correct 507 ms 830920 KB Output is correct
8 Correct 411 ms 830924 KB Output is correct
9 Correct 402 ms 830856 KB Output is correct
10 Correct 381 ms 830932 KB Output is correct
11 Correct 578 ms 830952 KB Output is correct
12 Correct 612 ms 831060 KB Output is correct
13 Correct 526 ms 830896 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29268 KB Output is correct
2 Correct 433 ms 830912 KB Output is correct
3 Correct 418 ms 830860 KB Output is correct
4 Correct 387 ms 830912 KB Output is correct
5 Correct 389 ms 830956 KB Output is correct
6 Correct 505 ms 830912 KB Output is correct
7 Correct 507 ms 830920 KB Output is correct
8 Correct 411 ms 830924 KB Output is correct
9 Correct 402 ms 830856 KB Output is correct
10 Correct 381 ms 830932 KB Output is correct
11 Correct 578 ms 830952 KB Output is correct
12 Correct 612 ms 831060 KB Output is correct
13 Correct 526 ms 830896 KB Output is correct
14 Correct 14 ms 29268 KB Output is correct
15 Correct 444 ms 830900 KB Output is correct
16 Correct 476 ms 830940 KB Output is correct
17 Correct 397 ms 830896 KB Output is correct
18 Correct 428 ms 830920 KB Output is correct
19 Correct 550 ms 832220 KB Output is correct
20 Correct 463 ms 831916 KB Output is correct
21 Correct 484 ms 832104 KB Output is correct
22 Correct 417 ms 832056 KB Output is correct
23 Correct 512 ms 832220 KB Output is correct
24 Correct 633 ms 832228 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29268 KB Output is correct
2 Correct 433 ms 830912 KB Output is correct
3 Correct 418 ms 830860 KB Output is correct
4 Correct 387 ms 830912 KB Output is correct
5 Correct 389 ms 830956 KB Output is correct
6 Correct 505 ms 830912 KB Output is correct
7 Correct 507 ms 830920 KB Output is correct
8 Correct 411 ms 830924 KB Output is correct
9 Correct 402 ms 830856 KB Output is correct
10 Correct 381 ms 830932 KB Output is correct
11 Correct 578 ms 830952 KB Output is correct
12 Correct 612 ms 831060 KB Output is correct
13 Correct 526 ms 830896 KB Output is correct
14 Correct 14 ms 29268 KB Output is correct
15 Correct 444 ms 830900 KB Output is correct
16 Correct 476 ms 830940 KB Output is correct
17 Correct 397 ms 830896 KB Output is correct
18 Correct 428 ms 830920 KB Output is correct
19 Correct 550 ms 832220 KB Output is correct
20 Correct 463 ms 831916 KB Output is correct
21 Correct 484 ms 832104 KB Output is correct
22 Correct 417 ms 832056 KB Output is correct
23 Correct 512 ms 832220 KB Output is correct
24 Correct 633 ms 832228 KB Output is correct
25 Correct 424 ms 831432 KB Output is correct
26 Correct 476 ms 832628 KB Output is correct
27 Correct 452 ms 831960 KB Output is correct
28 Correct 443 ms 832096 KB Output is correct
29 Correct 491 ms 832408 KB Output is correct
30 Correct 521 ms 832136 KB Output is correct
31 Correct 499 ms 831972 KB Output is correct
32 Correct 616 ms 832112 KB Output is correct
33 Correct 975 ms 832204 KB Output is correct
34 Correct 2131 ms 832112 KB Output is correct
35 Correct 714 ms 832064 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29268 KB Output is correct
2 Runtime error 123 ms 14768 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -