oj.uz

Submission #618972

# Submission time Handle Problem Language Result Execution time Memory
618972 2022-08-02T08:42:52 Z SlavicG Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 589876 KB 
#include "dungeons.h"
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
const int N = 4e5 + 10, K = 30;
pair<ll, ll> jump_win[N][K], jump_lose[N][K];
ll sum_win[N][K];
ll sum_lose[N][K];
ll finish, S[N], P[N], W[N], L[N];
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    for(int i = 0; i < n; ++i) {
        S[i] = s[i], P[i] = p[i], W[i] = w[i], L[i] = l[i];
    }
    finish = n;
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < K; ++j) {
            jump_win[i][j] = {n, 1e17};
            jump_lose[i][j] = {n, 0};
        }
    }
    for(int i = 0; i < n; ++i) {
        jump_win[i][0] = {w[i], s[i]};
        sum_win[i][0] = s[i];

        sum_lose[i][0] = p[i];
        jump_lose[i][0] = {l[i], s[i]};
    }
    for(int j = 1; j < K; ++j) {
        for(int i = 0; i < n; ++i) {
            jump_win[i][j].first = jump_win[jump_win[i][j - 1].first][j - 1].first;
            sum_win[i][j] = sum_win[i][j - 1] + sum_win[jump_win[i][j - 1].first][j - 1];
            ll need1 = jump_win[i][j - 1].second;
            ll need2 = jump_win[jump_win[i][j - 1].first][j - 1].second - sum_win[i][j - 1];
            jump_win[i][j].second = max(need1, need2);

            jump_lose[i][j].first = jump_lose[jump_lose[i][j - 1].first][j - 1].first;
            sum_lose[i][j] = sum_lose[i][j - 1] + sum_lose[jump_lose[i][j - 1].first][j - 1];
            need1 = jump_lose[i][j - 1].second;
            need2 = jump_lose[jump_lose[i][j - 1].first][j - 1].second - sum_lose[i][j - 1];
            jump_lose[i][j].second = min(need1, need2);
        }
    }
}

long long simulate(int x, int z) {
    ll w = z;
    while(x < finish) {
        for(int j = K - 1; j >= 0; --j) {
            if(w >= jump_win[x][j].second) {
                w += sum_win[x][j];
                x = jump_win[x][j].first;
            }
        }
        if(x == finish) break;
        for(int j = K - 1; j >= 0; --j) {
            if(w < jump_lose[x][j].second) {
                w += sum_lose[x][j];
                x = jump_lose[x][j].first;
            }
        }
    }
    return w;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 376024 KB Output is correct
2 Correct 265 ms 376184 KB Output is correct
3 Correct 171 ms 377024 KB Output is correct
4 Correct 228 ms 402704 KB Output is correct
5 Correct 158 ms 377052 KB Output is correct
6 Correct 230 ms 402632 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 376588 KB Output is correct
2 Correct 855 ms 589876 KB Output is correct
3 Correct 900 ms 589840 KB Output is correct
4 Correct 1185 ms 589752 KB Output is correct
5 Correct 898 ms 589748 KB Output is correct
6 Correct 922 ms 589632 KB Output is correct
7 Correct 1008 ms 589636 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 376572 KB Output is correct
2 Correct 292 ms 403492 KB Output is correct
3 Correct 285 ms 403492 KB Output is correct
4 Correct 258 ms 403612 KB Output is correct
5 Correct 265 ms 403488 KB Output is correct
6 Correct 266 ms 403428 KB Output is correct
7 Correct 275 ms 403376 KB Output is correct
8 Correct 273 ms 403492 KB Output is correct
9 Correct 267 ms 403404 KB Output is correct
10 Correct 318 ms 403488 KB Output is correct
11 Correct 316 ms 403500 KB Output is correct
12 Correct 436 ms 403412 KB Output is correct
13 Correct 340 ms 403532 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 376572 KB Output is correct
2 Correct 292 ms 403492 KB Output is correct
3 Correct 285 ms 403492 KB Output is correct
4 Correct 258 ms 403612 KB Output is correct
5 Correct 265 ms 403488 KB Output is correct
6 Correct 266 ms 403428 KB Output is correct
7 Correct 275 ms 403376 KB Output is correct
8 Correct 273 ms 403492 KB Output is correct
9 Correct 267 ms 403404 KB Output is correct
10 Correct 318 ms 403488 KB Output is correct
11 Correct 316 ms 403500 KB Output is correct
12 Correct 436 ms 403412 KB Output is correct
13 Correct 340 ms 403532 KB Output is correct
14 Correct 172 ms 376588 KB Output is correct
15 Correct 475 ms 403496 KB Output is correct
16 Correct 272 ms 403616 KB Output is correct
17 Correct 292 ms 403492 KB Output is correct
18 Correct 321 ms 403476 KB Output is correct
19 Correct 312 ms 403420 KB Output is correct
20 Correct 287 ms 403556 KB Output is correct
21 Correct 280 ms 403484 KB Output is correct
22 Execution timed out 7117 ms 403496 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 376572 KB Output is correct
2 Correct 292 ms 403492 KB Output is correct
3 Correct 285 ms 403492 KB Output is correct
4 Correct 258 ms 403612 KB Output is correct
5 Correct 265 ms 403488 KB Output is correct
6 Correct 266 ms 403428 KB Output is correct
7 Correct 275 ms 403376 KB Output is correct
8 Correct 273 ms 403492 KB Output is correct
9 Correct 267 ms 403404 KB Output is correct
10 Correct 318 ms 403488 KB Output is correct
11 Correct 316 ms 403500 KB Output is correct
12 Correct 436 ms 403412 KB Output is correct
13 Correct 340 ms 403532 KB Output is correct
14 Correct 172 ms 376588 KB Output is correct
15 Correct 475 ms 403496 KB Output is correct
16 Correct 272 ms 403616 KB Output is correct
17 Correct 292 ms 403492 KB Output is correct
18 Correct 321 ms 403476 KB Output is correct
19 Correct 312 ms 403420 KB Output is correct
20 Correct 287 ms 403556 KB Output is correct
21 Correct 280 ms 403484 KB Output is correct
22 Execution timed out 7117 ms 403496 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 376588 KB Output is correct
2 Correct 855 ms 589876 KB Output is correct
3 Correct 900 ms 589840 KB Output is correct
4 Correct 1185 ms 589752 KB Output is correct
5 Correct 898 ms 589748 KB Output is correct
6 Correct 922 ms 589632 KB Output is correct
7 Correct 1008 ms 589636 KB Output is correct
8 Correct 173 ms 376572 KB Output is correct
9 Correct 292 ms 403492 KB Output is correct
10 Correct 285 ms 403492 KB Output is correct
11 Correct 258 ms 403612 KB Output is correct
12 Correct 265 ms 403488 KB Output is correct
13 Correct 266 ms 403428 KB Output is correct
14 Correct 275 ms 403376 KB Output is correct
15 Correct 273 ms 403492 KB Output is correct
16 Correct 267 ms 403404 KB Output is correct
17 Correct 318 ms 403488 KB Output is correct
18 Correct 316 ms 403500 KB Output is correct
19 Correct 436 ms 403412 KB Output is correct
20 Correct 340 ms 403532 KB Output is correct
21 Correct 172 ms 376588 KB Output is correct
22 Correct 475 ms 403496 KB Output is correct
23 Correct 272 ms 403616 KB Output is correct
24 Correct 292 ms 403492 KB Output is correct
25 Correct 321 ms 403476 KB Output is correct
26 Correct 312 ms 403420 KB Output is correct
27 Correct 287 ms 403556 KB Output is correct
28 Correct 280 ms 403484 KB Output is correct
29 Execution timed out 7117 ms 403496 KB Time limit exceeded
30 Halted 0 ms 0 KB -