oj.uz

Submission #609832

# Submission time Handle Problem Language Result Execution time Memory
609832 2022-07-28T00:45:31 Z duality Dungeons Game (IOI21_dungeons) C++17
100 / 100
 2131 ms 976720 KB 
#define DEBUG 0

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

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
#include "dungeons.h"

int N,S[400000],P[400000],W[400000],L[400000];
int nxt[8][19][400000],mm[8][19][400000];
LLI add[8][19][400000];
void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l) {
    int i,j,k,pp = 1;
    N = n;
    for (i = 0; i < n; i++) S[i] = s[i],P[i] = p[i],W[i] = w[i],L[i] = l[i];
    for (i = 0; i < 8; i++) {
        for (j = 0; j < n; j++) {
            if (S[j] <= pp) nxt[i][0][j] = W[j],add[i][0][j] = S[j],mm[i][0][j] = 1e9;
            else nxt[i][0][j] = L[j],add[i][0][j] = P[j],mm[i][0][j] = S[j];
        }
        for (j = 1; j < 19; j++) {
            for (k = 0; k < n; k++) {
                if (nxt[i][j-1][k] != n) {
                    nxt[i][j][k] = nxt[i][j-1][nxt[i][j-1][k]];
                    add[i][j][k] = add[i][j-1][k]+add[i][j-1][nxt[i][j-1][k]];
                    if (mm[i][j-1][nxt[i][j-1][k]] == 1e9) mm[i][j][k] = mm[i][j-1][k];
                    else mm[i][j][k] = min(mm[i][j-1][k],(int) max(mm[i][j-1][nxt[i][j-1][k]]-add[i][j-1][k],0LL));
                }
                else nxt[i][j][k] = n;
            }
        }
        pp *= 10;
    }
}
long long int simulate(int x,int z) {
    int i,j,l = 0,pp = 1;
    LLI s = z;
    while (x != N) {
        while ((l < 7) && (10*pp <= s)) l++,pp *= 10;
        for (i = 18; i >= 0; i--) {
            if ((nxt[l][i][x] != N) && (min(s,(LLI) 1e7) < mm[l][i][x])) s += add[l][i][x],x = nxt[l][i][x];
        }
        if (s >= S[x]) s += S[x],x = W[x];
        else s += P[x],x = L[x];
    }
    return s;
}

Compilation message

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:86:11: warning: unused variable 'j' [-Wunused-variable]
   86 |     int i,j,l = 0,pp = 1;
      |           ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2516 KB Output is correct
2 Correct 2 ms 2612 KB Output is correct
3 Correct 5 ms 5056 KB Output is correct
4 Correct 80 ms 94472 KB Output is correct
5 Correct 4 ms 6484 KB Output is correct
6 Correct 65 ms 94504 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5824 KB Output is correct
2 Correct 715 ms 969636 KB Output is correct
3 Correct 662 ms 970420 KB Output is correct
4 Correct 677 ms 967344 KB Output is correct
5 Correct 706 ms 853964 KB Output is correct
6 Correct 694 ms 971712 KB Output is correct
7 Correct 665 ms 973068 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5844 KB Output is correct
2 Correct 149 ms 118744 KB Output is correct
3 Correct 140 ms 124520 KB Output is correct
4 Correct 101 ms 112872 KB Output is correct
5 Correct 110 ms 109956 KB Output is correct
6 Correct 165 ms 118812 KB Output is correct
7 Correct 279 ms 118728 KB Output is correct
8 Correct 135 ms 112780 KB Output is correct
9 Correct 88 ms 71560 KB Output is correct
10 Correct 116 ms 112784 KB Output is correct
11 Correct 120 ms 112748 KB Output is correct
12 Correct 1567 ms 121268 KB Output is correct
13 Correct 1597 ms 115812 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5844 KB Output is correct
2 Correct 149 ms 118744 KB Output is correct
3 Correct 140 ms 124520 KB Output is correct
4 Correct 101 ms 112872 KB Output is correct
5 Correct 110 ms 109956 KB Output is correct
6 Correct 165 ms 118812 KB Output is correct
7 Correct 279 ms 118728 KB Output is correct
8 Correct 135 ms 112780 KB Output is correct
9 Correct 88 ms 71560 KB Output is correct
10 Correct 116 ms 112784 KB Output is correct
11 Correct 120 ms 112748 KB Output is correct
12 Correct 1567 ms 121268 KB Output is correct
13 Correct 1597 ms 115812 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 115 ms 118728 KB Output is correct
16 Correct 195 ms 118688 KB Output is correct
17 Correct 105 ms 123960 KB Output is correct
18 Correct 114 ms 123936 KB Output is correct
19 Correct 178 ms 118788 KB Output is correct
20 Correct 160 ms 124288 KB Output is correct
21 Correct 130 ms 124236 KB Output is correct
22 Correct 127 ms 104668 KB Output is correct
23 Correct 144 ms 115916 KB Output is correct
24 Correct 304 ms 115816 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5844 KB Output is correct
2 Correct 149 ms 118744 KB Output is correct
3 Correct 140 ms 124520 KB Output is correct
4 Correct 101 ms 112872 KB Output is correct
5 Correct 110 ms 109956 KB Output is correct
6 Correct 165 ms 118812 KB Output is correct
7 Correct 279 ms 118728 KB Output is correct
8 Correct 135 ms 112780 KB Output is correct
9 Correct 88 ms 71560 KB Output is correct
10 Correct 116 ms 112784 KB Output is correct
11 Correct 120 ms 112748 KB Output is correct
12 Correct 1567 ms 121268 KB Output is correct
13 Correct 1597 ms 115812 KB Output is correct
14 Correct 4 ms 5844 KB Output is correct
15 Correct 115 ms 118728 KB Output is correct
16 Correct 195 ms 118688 KB Output is correct
17 Correct 105 ms 123960 KB Output is correct
18 Correct 114 ms 123936 KB Output is correct
19 Correct 178 ms 118788 KB Output is correct
20 Correct 160 ms 124288 KB Output is correct
21 Correct 130 ms 124236 KB Output is correct
22 Correct 127 ms 104668 KB Output is correct
23 Correct 144 ms 115916 KB Output is correct
24 Correct 304 ms 115816 KB Output is correct
25 Correct 88 ms 118204 KB Output is correct
26 Correct 176 ms 118860 KB Output is correct
27 Correct 125 ms 118700 KB Output is correct
28 Correct 123 ms 118772 KB Output is correct
29 Correct 148 ms 118924 KB Output is correct
30 Correct 146 ms 124672 KB Output is correct
31 Correct 152 ms 124116 KB Output is correct
32 Correct 220 ms 115332 KB Output is correct
33 Correct 733 ms 121088 KB Output is correct
34 Correct 1049 ms 121404 KB Output is correct
35 Correct 494 ms 119644 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5824 KB Output is correct
2 Correct 715 ms 969636 KB Output is correct
3 Correct 662 ms 970420 KB Output is correct
4 Correct 677 ms 967344 KB Output is correct
5 Correct 706 ms 853964 KB Output is correct
6 Correct 694 ms 971712 KB Output is correct
7 Correct 665 ms 973068 KB Output is correct
8 Correct 5 ms 5844 KB Output is correct
9 Correct 149 ms 118744 KB Output is correct
10 Correct 140 ms 124520 KB Output is correct
11 Correct 101 ms 112872 KB Output is correct
12 Correct 110 ms 109956 KB Output is correct
13 Correct 165 ms 118812 KB Output is correct
14 Correct 279 ms 118728 KB Output is correct
15 Correct 135 ms 112780 KB Output is correct
16 Correct 88 ms 71560 KB Output is correct
17 Correct 116 ms 112784 KB Output is correct
18 Correct 120 ms 112748 KB Output is correct
19 Correct 1567 ms 121268 KB Output is correct
20 Correct 1597 ms 115812 KB Output is correct
21 Correct 4 ms 5844 KB Output is correct
22 Correct 115 ms 118728 KB Output is correct
23 Correct 195 ms 118688 KB Output is correct
24 Correct 105 ms 123960 KB Output is correct
25 Correct 114 ms 123936 KB Output is correct
26 Correct 178 ms 118788 KB Output is correct
27 Correct 160 ms 124288 KB Output is correct
28 Correct 130 ms 124236 KB Output is correct
29 Correct 127 ms 104668 KB Output is correct
30 Correct 144 ms 115916 KB Output is correct
31 Correct 304 ms 115816 KB Output is correct
32 Correct 88 ms 118204 KB Output is correct
33 Correct 176 ms 118860 KB Output is correct
34 Correct 125 ms 118700 KB Output is correct
35 Correct 123 ms 118772 KB Output is correct
36 Correct 148 ms 118924 KB Output is correct
37 Correct 146 ms 124672 KB Output is correct
38 Correct 152 ms 124116 KB Output is correct
39 Correct 220 ms 115332 KB Output is correct
40 Correct 733 ms 121088 KB Output is correct
41 Correct 1049 ms 121404 KB Output is correct
42 Correct 494 ms 119644 KB Output is correct
43 Correct 1 ms 1876 KB Output is correct
44 Correct 4 ms 5808 KB Output is correct
45 Correct 989 ms 921568 KB Output is correct
46 Correct 800 ms 917568 KB Output is correct
47 Correct 737 ms 917944 KB Output is correct
48 Correct 726 ms 976720 KB Output is correct
49 Correct 1058 ms 922340 KB Output is correct
50 Correct 697 ms 976344 KB Output is correct
51 Correct 841 ms 975184 KB Output is correct
52 Correct 710 ms 974460 KB Output is correct
53 Correct 1294 ms 913856 KB Output is correct
54 Correct 1476 ms 955476 KB Output is correct
55 Correct 1919 ms 956820 KB Output is correct
56 Correct 1693 ms 952084 KB Output is correct
57 Correct 1687 ms 947772 KB Output is correct
58 Correct 2131 ms 947780 KB Output is correct
59 Correct 1914 ms 947868 KB Output is correct
60 Correct 1601 ms 969908 KB Output is correct
61 Correct 1527 ms 956412 KB Output is correct