oj.uz

Submission #612568

# Submission time Handle Problem Language Result Execution time Memory
612568 2022-07-29T17:44:38 Z AmirElarbi Dungeons Game (IOI21_dungeons) C++17
100 / 100
 5629 ms 1283960 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 2e9+5
#define eps 1e-7
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
#define V 450
using namespace std;
const int MOD = 1e9;
const int nax = 4e5+5;
const int lg = 20;
//#include "dungeons.h"
int nxt[8][nax][lg], n;
vi s,p,w,l;
ll sm[8][nax][lg], mn[8][nax][lg];
void init(int N, vi S, vi P, vi W, vi L) {
    n = N; 
    s = S, p = P, w = W, l = L;
    s.pb(0), p.pb(0);
    for (int i = 0; i < lg; ++i)
    {
        for(int j =0; j < 8; j++) nxt[j][n][i] = n, sm[j][n][i] = 0, mn[j][n][i] = 1e9;
    }
    int cur = 1;
    for(int ind = 0; ind < 8; ind++){
        for (int i = 0; i < n; ++i)
        {
            if(cur >= s[i]) nxt[ind][i][0] = w[i], sm[ind][i][0] = s[i], mn[ind][i][0] = 1e9;
            else nxt[ind][i][0] = l[i], sm[ind][i][0] = p[i], mn[ind][i][0] =s[i];     
        }
        for (int j = 1; j < lg; ++j){
            for (int i = n-1; i >= 0; --i)
            {
                nxt[ind][i][j] = nxt[ind][nxt[ind][i][j-1]][j-1];
                sm[ind][i][j] = sm[ind][i][j-1] + sm[ind][nxt[ind][i][j-1]][j-1];
                if(mn[ind][nxt[ind][i][j-1]][j-1] == 1e9) mn[ind][i][j] = mn[ind][i][j-1];
                else mn[ind][i][j] = min(mn[ind][i][j-1], max(mn[ind][nxt[ind][i][j-1]][j-1] - sm[ind][i][j-1],0ll));
            }
        } 
        cur *= 10;
    }
}

long long simulate(int x, int z) {
    ll ind = 0, cur = 1, val = z;
    while(x != n){
        while(ind < 7 && 10*cur <= val) ind++, cur *= 10;
        for (int i = 0; i < lg; ++i)
        {
            if(min(val,(ll)(1e7)) < mn[ind][x][i]){
                val += sm[ind][x][i];
                x = nxt[ind][x][i];
            }
        }
        if(x == n) break;
        if(val >= s[x]) val += s[x], x = w[x];
        else val += p[x], x = l[x];   
    }
    return val;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 5 ms 6868 KB Output is correct
4 Correct 256 ms 159300 KB Output is correct
5 Correct 5 ms 6796 KB Output is correct
6 Correct 343 ms 159400 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3668 KB Output is correct
2 Correct 2622 ms 1272300 KB Output is correct
3 Correct 2614 ms 1272348 KB Output is correct
4 Correct 2404 ms 1272244 KB Output is correct
5 Correct 2321 ms 1272344 KB Output is correct
6 Correct 2776 ms 1272248 KB Output is correct
7 Correct 2678 ms 1272272 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3668 KB Output is correct
2 Correct 343 ms 160116 KB Output is correct
3 Correct 363 ms 160252 KB Output is correct
4 Correct 347 ms 160152 KB Output is correct
5 Correct 337 ms 160180 KB Output is correct
6 Correct 399 ms 160068 KB Output is correct
7 Correct 419 ms 160132 KB Output is correct
8 Correct 368 ms 160116 KB Output is correct
9 Correct 351 ms 160068 KB Output is correct
10 Correct 370 ms 160184 KB Output is correct
11 Correct 401 ms 160180 KB Output is correct
12 Correct 1702 ms 160128 KB Output is correct
13 Correct 1395 ms 160168 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3668 KB Output is correct
2 Correct 343 ms 160116 KB Output is correct
3 Correct 363 ms 160252 KB Output is correct
4 Correct 347 ms 160152 KB Output is correct
5 Correct 337 ms 160180 KB Output is correct
6 Correct 399 ms 160068 KB Output is correct
7 Correct 419 ms 160132 KB Output is correct
8 Correct 368 ms 160116 KB Output is correct
9 Correct 351 ms 160068 KB Output is correct
10 Correct 370 ms 160184 KB Output is correct
11 Correct 401 ms 160180 KB Output is correct
12 Correct 1702 ms 160128 KB Output is correct
13 Correct 1395 ms 160168 KB Output is correct
14 Correct 4 ms 3668 KB Output is correct
15 Correct 326 ms 160124 KB Output is correct
16 Correct 350 ms 160228 KB Output is correct
17 Correct 402 ms 160072 KB Output is correct
18 Correct 429 ms 160192 KB Output is correct
19 Correct 398 ms 160196 KB Output is correct
20 Correct 444 ms 160268 KB Output is correct
21 Correct 432 ms 160184 KB Output is correct
22 Correct 380 ms 160200 KB Output is correct
23 Correct 497 ms 160100 KB Output is correct
24 Correct 1028 ms 160068 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3668 KB Output is correct
2 Correct 343 ms 160116 KB Output is correct
3 Correct 363 ms 160252 KB Output is correct
4 Correct 347 ms 160152 KB Output is correct
5 Correct 337 ms 160180 KB Output is correct
6 Correct 399 ms 160068 KB Output is correct
7 Correct 419 ms 160132 KB Output is correct
8 Correct 368 ms 160116 KB Output is correct
9 Correct 351 ms 160068 KB Output is correct
10 Correct 370 ms 160184 KB Output is correct
11 Correct 401 ms 160180 KB Output is correct
12 Correct 1702 ms 160128 KB Output is correct
13 Correct 1395 ms 160168 KB Output is correct
14 Correct 4 ms 3668 KB Output is correct
15 Correct 326 ms 160124 KB Output is correct
16 Correct 350 ms 160228 KB Output is correct
17 Correct 402 ms 160072 KB Output is correct
18 Correct 429 ms 160192 KB Output is correct
19 Correct 398 ms 160196 KB Output is correct
20 Correct 444 ms 160268 KB Output is correct
21 Correct 432 ms 160184 KB Output is correct
22 Correct 380 ms 160200 KB Output is correct
23 Correct 497 ms 160100 KB Output is correct
24 Correct 1028 ms 160068 KB Output is correct
25 Correct 281 ms 159364 KB Output is correct
26 Correct 379 ms 160128 KB Output is correct
27 Correct 345 ms 160204 KB Output is correct
28 Correct 330 ms 160092 KB Output is correct
29 Correct 347 ms 160100 KB Output is correct
30 Correct 603 ms 160160 KB Output is correct
31 Correct 574 ms 160180 KB Output is correct
32 Correct 814 ms 160164 KB Output is correct
33 Correct 741 ms 160128 KB Output is correct
34 Correct 1227 ms 160012 KB Output is correct
35 Correct 914 ms 160140 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3668 KB Output is correct
2 Correct 2622 ms 1272300 KB Output is correct
3 Correct 2614 ms 1272348 KB Output is correct
4 Correct 2404 ms 1272244 KB Output is correct
5 Correct 2321 ms 1272344 KB Output is correct
6 Correct 2776 ms 1272248 KB Output is correct
7 Correct 2678 ms 1272272 KB Output is correct
8 Correct 5 ms 3668 KB Output is correct
9 Correct 343 ms 160116 KB Output is correct
10 Correct 363 ms 160252 KB Output is correct
11 Correct 347 ms 160152 KB Output is correct
12 Correct 337 ms 160180 KB Output is correct
13 Correct 399 ms 160068 KB Output is correct
14 Correct 419 ms 160132 KB Output is correct
15 Correct 368 ms 160116 KB Output is correct
16 Correct 351 ms 160068 KB Output is correct
17 Correct 370 ms 160184 KB Output is correct
18 Correct 401 ms 160180 KB Output is correct
19 Correct 1702 ms 160128 KB Output is correct
20 Correct 1395 ms 160168 KB Output is correct
21 Correct 4 ms 3668 KB Output is correct
22 Correct 326 ms 160124 KB Output is correct
23 Correct 350 ms 160228 KB Output is correct
24 Correct 402 ms 160072 KB Output is correct
25 Correct 429 ms 160192 KB Output is correct
26 Correct 398 ms 160196 KB Output is correct
27 Correct 444 ms 160268 KB Output is correct
28 Correct 432 ms 160184 KB Output is correct
29 Correct 380 ms 160200 KB Output is correct
30 Correct 497 ms 160100 KB Output is correct
31 Correct 1028 ms 160068 KB Output is correct
32 Correct 281 ms 159364 KB Output is correct
33 Correct 379 ms 160128 KB Output is correct
34 Correct 345 ms 160204 KB Output is correct
35 Correct 330 ms 160092 KB Output is correct
36 Correct 347 ms 160100 KB Output is correct
37 Correct 603 ms 160160 KB Output is correct
38 Correct 574 ms 160180 KB Output is correct
39 Correct 814 ms 160164 KB Output is correct
40 Correct 741 ms 160128 KB Output is correct
41 Correct 1227 ms 160012 KB Output is correct
42 Correct 914 ms 160140 KB Output is correct
43 Correct 1 ms 468 KB Output is correct
44 Correct 5 ms 3716 KB Output is correct
45 Correct 3036 ms 1272256 KB Output is correct
46 Correct 2349 ms 1272352 KB Output is correct
47 Correct 2332 ms 1272300 KB Output is correct
48 Correct 2358 ms 1272356 KB Output is correct
49 Correct 2693 ms 1283960 KB Output is correct
50 Correct 2764 ms 1281460 KB Output is correct
51 Correct 2301 ms 1281924 KB Output is correct
52 Correct 2751 ms 1279632 KB Output is correct
53 Correct 4358 ms 1280284 KB Output is correct
54 Correct 3148 ms 1281492 KB Output is correct
55 Correct 3899 ms 1280528 KB Output is correct
56 Correct 3793 ms 1281164 KB Output is correct
57 Correct 3926 ms 1281220 KB Output is correct
58 Correct 4674 ms 1281236 KB Output is correct
59 Correct 4533 ms 1281372 KB Output is correct
60 Correct 4998 ms 1280600 KB Output is correct
61 Correct 5629 ms 1280656 KB Output is correct