oj.uz

Submission #929107

# Submission time Handle Problem Language Result Execution time Memory
929107 2024-02-17T17:25:50 Z abcvuitunggio Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 1907184 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int base=10,sz=9;
const long long INF=1e18;
int N,nxt[400001][24][sz+1];
long long mx[400001][24],mn[400001][24][sz],sum[400001][24][sz+1];
vector <int> S,P,ve={1};
void init(int n, vector <int> s, vector <int> p, vector <int> w, vector <int> l){
    N=n,S=s,P=p;
    for (int i=1;i<sz;i++)
        ve.push_back(ve.back()*base);
    memset(nxt,-1,sizeof(nxt));
    for (int i=0;i<n;i++){
        for (int j=0;j<sz;j++)
            if (s[i]<=ve[j]){
                nxt[i][0][j]=w[i];
                sum[i][0][j]=s[i];
                mn[i][0][j]=INF;
            }
            else{
                nxt[i][0][j]=l[i];
                sum[i][0][j]=p[i];
                mn[i][0][j]=s[i];
            }
        nxt[i][0][sz]=w[i];
        mx[i][0]=sum[i][0][sz]=s[i];
    }
    for (int j=1;j<24;j++){
        for (int i=0;i<n;i++)
            for (int k=0;k<=sz;k++){
                if (nxt[i][j-1][k]==-1)
                    continue;
                int u=nxt[i][j-1][k];
                nxt[i][j][k]=nxt[u][j-1][k];
                if (k<sz)
                    mn[i][j][k]=min(mn[i][j-1][k],mn[u][j-1][k]-sum[i][j-1][k]);
                else
                    mx[i][j]=max(mx[i][j-1],mx[u][j-1]-sum[i][j-1][k]);
                sum[i][j][k]=sum[i][j-1][k]+sum[u][j-1][k];
            }
    }
}
long long simulate(int x, int Z){
    int b=0,cur=0;
    long long z=Z;
    while (x<N){
        while (cur<sz&&ve[cur]<=z)
            cur++;
        int j=(b?cur-1:sz);
        for (int i=23;i>=0;i--)
            if (nxt[x][i][j]!=-1)
                if ((b&&z<mn[x][i][j])||(!b&&z>=mx[x][i])){
                    z+=sum[x][i][j];
                    x=nxt[x][i][j];
                }
        b^=1;
    }
    return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 376132 KB Output is correct
2 Correct 124 ms 376148 KB Output is correct
3 Correct 54 ms 387392 KB Output is correct
4 Correct 421 ms 569188 KB Output is correct
5 Correct 125 ms 383572 KB Output is correct
6 Correct 444 ms 566772 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 379792 KB Output is correct
2 Correct 4132 ms 1897480 KB Output is correct
3 Correct 3745 ms 1899628 KB Output is correct
4 Correct 3571 ms 1903440 KB Output is correct
5 Correct 3198 ms 1903984 KB Output is correct
6 Correct 3685 ms 1902448 KB Output is correct
7 Correct 3469 ms 1900656 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 380012 KB Output is correct
2 Correct 526 ms 568312 KB Output is correct
3 Correct 526 ms 568564 KB Output is correct
4 Correct 493 ms 567736 KB Output is correct
5 Correct 478 ms 567804 KB Output is correct
6 Correct 527 ms 567892 KB Output is correct
7 Correct 535 ms 568056 KB Output is correct
8 Correct 313 ms 573672 KB Output is correct
9 Correct 292 ms 568400 KB Output is correct
10 Correct 490 ms 569104 KB Output is correct
11 Correct 564 ms 568912 KB Output is correct
12 Correct 770 ms 568896 KB Output is correct
13 Correct 597 ms 568744 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 380012 KB Output is correct
2 Correct 526 ms 568312 KB Output is correct
3 Correct 526 ms 568564 KB Output is correct
4 Correct 493 ms 567736 KB Output is correct
5 Correct 478 ms 567804 KB Output is correct
6 Correct 527 ms 567892 KB Output is correct
7 Correct 535 ms 568056 KB Output is correct
8 Correct 313 ms 573672 KB Output is correct
9 Correct 292 ms 568400 KB Output is correct
10 Correct 490 ms 569104 KB Output is correct
11 Correct 564 ms 568912 KB Output is correct
12 Correct 770 ms 568896 KB Output is correct
13 Correct 597 ms 568744 KB Output is correct
14 Correct 61 ms 383084 KB Output is correct
15 Correct 516 ms 568184 KB Output is correct
16 Correct 575 ms 568468 KB Output is correct
17 Correct 552 ms 567892 KB Output is correct
18 Correct 549 ms 567932 KB Output is correct
19 Correct 471 ms 571512 KB Output is correct
20 Correct 578 ms 568012 KB Output is correct
21 Correct 571 ms 568652 KB Output is correct
22 Correct 512 ms 568620 KB Output is correct
23 Correct 582 ms 568752 KB Output is correct
24 Correct 761 ms 568912 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 380012 KB Output is correct
2 Correct 526 ms 568312 KB Output is correct
3 Correct 526 ms 568564 KB Output is correct
4 Correct 493 ms 567736 KB Output is correct
5 Correct 478 ms 567804 KB Output is correct
6 Correct 527 ms 567892 KB Output is correct
7 Correct 535 ms 568056 KB Output is correct
8 Correct 313 ms 573672 KB Output is correct
9 Correct 292 ms 568400 KB Output is correct
10 Correct 490 ms 569104 KB Output is correct
11 Correct 564 ms 568912 KB Output is correct
12 Correct 770 ms 568896 KB Output is correct
13 Correct 597 ms 568744 KB Output is correct
14 Correct 61 ms 383084 KB Output is correct
15 Correct 516 ms 568184 KB Output is correct
16 Correct 575 ms 568468 KB Output is correct
17 Correct 552 ms 567892 KB Output is correct
18 Correct 549 ms 567932 KB Output is correct
19 Correct 471 ms 571512 KB Output is correct
20 Correct 578 ms 568012 KB Output is correct
21 Correct 571 ms 568652 KB Output is correct
22 Correct 512 ms 568620 KB Output is correct
23 Correct 582 ms 568752 KB Output is correct
24 Correct 761 ms 568912 KB Output is correct
25 Correct 403 ms 568144 KB Output is correct
26 Correct 440 ms 569004 KB Output is correct
27 Correct 436 ms 568500 KB Output is correct
28 Correct 413 ms 568496 KB Output is correct
29 Correct 452 ms 568912 KB Output is correct
30 Correct 429 ms 573832 KB Output is correct
31 Correct 576 ms 567892 KB Output is correct
32 Correct 683 ms 567928 KB Output is correct
33 Correct 1615 ms 567996 KB Output is correct
34 Correct 1722 ms 567632 KB Output is correct
35 Correct 857 ms 567928 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 379792 KB Output is correct
2 Correct 4132 ms 1897480 KB Output is correct
3 Correct 3745 ms 1899628 KB Output is correct
4 Correct 3571 ms 1903440 KB Output is correct
5 Correct 3198 ms 1903984 KB Output is correct
6 Correct 3685 ms 1902448 KB Output is correct
7 Correct 3469 ms 1900656 KB Output is correct
8 Correct 146 ms 380012 KB Output is correct
9 Correct 526 ms 568312 KB Output is correct
10 Correct 526 ms 568564 KB Output is correct
11 Correct 493 ms 567736 KB Output is correct
12 Correct 478 ms 567804 KB Output is correct
13 Correct 527 ms 567892 KB Output is correct
14 Correct 535 ms 568056 KB Output is correct
15 Correct 313 ms 573672 KB Output is correct
16 Correct 292 ms 568400 KB Output is correct
17 Correct 490 ms 569104 KB Output is correct
18 Correct 564 ms 568912 KB Output is correct
19 Correct 770 ms 568896 KB Output is correct
20 Correct 597 ms 568744 KB Output is correct
21 Correct 61 ms 383084 KB Output is correct
22 Correct 516 ms 568184 KB Output is correct
23 Correct 575 ms 568468 KB Output is correct
24 Correct 552 ms 567892 KB Output is correct
25 Correct 549 ms 567932 KB Output is correct
26 Correct 471 ms 571512 KB Output is correct
27 Correct 578 ms 568012 KB Output is correct
28 Correct 571 ms 568652 KB Output is correct
29 Correct 512 ms 568620 KB Output is correct
30 Correct 582 ms 568752 KB Output is correct
31 Correct 761 ms 568912 KB Output is correct
32 Correct 403 ms 568144 KB Output is correct
33 Correct 440 ms 569004 KB Output is correct
34 Correct 436 ms 568500 KB Output is correct
35 Correct 413 ms 568496 KB Output is correct
36 Correct 452 ms 568912 KB Output is correct
37 Correct 429 ms 573832 KB Output is correct
38 Correct 576 ms 567892 KB Output is correct
39 Correct 683 ms 567928 KB Output is correct
40 Correct 1615 ms 567996 KB Output is correct
41 Correct 1722 ms 567632 KB Output is correct
42 Correct 857 ms 567928 KB Output is correct
43 Correct 46 ms 380756 KB Output is correct
44 Correct 64 ms 383276 KB Output is correct
45 Correct 3488 ms 1907184 KB Output is correct
46 Correct 2837 ms 1902576 KB Output is correct
47 Correct 3188 ms 1902956 KB Output is correct
48 Correct 2704 ms 1905128 KB Output is correct
49 Correct 3220 ms 1907180 KB Output is correct
50 Correct 3149 ms 1904744 KB Output is correct
51 Correct 2627 ms 1905128 KB Output is correct
52 Correct 3272 ms 1902824 KB Output is correct
53 Correct 6200 ms 1903600 KB Output is correct
54 Correct 4876 ms 1904888 KB Output is correct
55 Correct 4931 ms 1903720 KB Output is correct
56 Correct 5049 ms 1904484 KB Output is correct
57 Correct 6817 ms 1904364 KB Output is correct
58 Execution timed out 7175 ms 1902960 KB Time limit exceeded
59 Halted 0 ms 0 KB -