oj.uz

Submission #631216

# Submission time Handle Problem Language Result Execution time Memory
631216 2022-08-17T20:39:48 Z qwerasdfzxcl Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3729 ms 1058496 KB 
#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int S = 8, T = 8, L = 24, L2 = 20, MX = 400002, INF = 1e9+100;
struct Node{
    int s, c, val;
    Node(){}
    Node(int _s, int _c, int _v): s(_s), c(_c), val(_v) {}
    Node operator + (const Node &S) const{
        assert((ll)c + S.c <= INF);
        return Node(S.s, c+S.c, min(val, S.val-c));
    }
}sp1[L][T][MX];
pair<int, ll> sp2[L2][MX];
int n;

pair<int, ll> operator + (const pair<int, ll> &a, const pair<int, ll> &b){return {b.first, a.second+b.second};}

vector<int> is, ip, iw, il;
void init(int N, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
    is = s, ip = p, iw = w, il = l;

    n = N;
    for (int i=0;i<L;i++){

        for (int v=0;v<n;v++){
            if (s[v]<=(1<<i)) sp1[i][0][v] = Node(w[v], s[v], INF);
            else sp1[i][0][v] = Node(l[v], p[v], s[v]);
        }

        for (int j=1;j<T;j++){
            for (int v=0;v<n;v++){
                sp1[i][j][v] = sp1[i][j-1][v];
                if (sp1[i][j-1][v].s==n || sp1[i][j-1][v].c >= (1<<i)) continue;

                for (int t=0;t<S-1;t++){
                    int cur = sp1[i][j][v].s;
                    sp1[i][j][v] = sp1[i][j][v] + sp1[i][j-1][cur];
                    if (sp1[i][j][v].s==n || sp1[i][j][v].c >= (1<<i)) break;
                }
            }
        }
    }

    for (int v=0;v<n;v++) sp2[0][v] = {w[v], s[v]};
    for (int j=1;j<L2;j++){
        for (int v=0;v<n;v++){
            sp2[j][v] = sp2[j-1][v];
            if (sp2[j][v].first==n) continue;
            sp2[j][v] = sp2[j][v] + sp2[j-1][sp2[j-1][v].first];
        }
    }
}

long long simulate(int pos, int mp0) {
    ll mp = mp0;
    for (int i=0;i<L;i++){
        if (mp >= (1<<(i+1))) continue;

        Node cur(pos, 0, INF);
        for (int j=T-1;j>=0;j--){
            int loop = 0;
            while(true){
                assert(++loop <= S+2);
                Node nxt = cur + sp1[i][j][cur.s];
                if (nxt.s == n || nxt.c >= ((1<<(i+1))-mp) || mp >= nxt.val) break;
                cur = nxt;
            }
        }

        pos = cur.s;
        mp += cur.c;
        assert(pos!=n && mp < (1<<(i+1)));

        if (mp >= is[pos]){mp += is[pos]; pos = iw[pos];}
        else {mp += ip[pos]; pos = il[pos];}
        if (pos==n) return mp;

        assert(mp >= (1<<(i+1)));
    }

    for (int j=L2-1;j>=0;j--) if (sp2[j][pos].first!=n){
        mp += sp2[j][pos].second;
        pos = sp2[j][pos].first;
    }

    assert(pos!=n);
    assert(sp2[0][pos].first==n);
	return mp + sp2[0][pos].second;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2004 KB Output is correct
2 Correct 1 ms 2004 KB Output is correct
3 Correct 6 ms 7252 KB Output is correct
4 Correct 102 ms 133740 KB Output is correct
5 Correct 7 ms 7168 KB Output is correct
6 Correct 162 ms 133580 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4564 KB Output is correct
2 Correct 1619 ms 1053764 KB Output is correct
3 Correct 1598 ms 1053884 KB Output is correct
4 Correct 1268 ms 1055256 KB Output is correct
5 Correct 987 ms 1055476 KB Output is correct
6 Correct 2745 ms 1053936 KB Output is correct
7 Correct 2549 ms 1051984 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4564 KB Output is correct
2 Correct 120 ms 135104 KB Output is correct
3 Correct 140 ms 135272 KB Output is correct
4 Correct 223 ms 134648 KB Output is correct
5 Correct 216 ms 134560 KB Output is correct
6 Correct 475 ms 134808 KB Output is correct
7 Correct 666 ms 134744 KB Output is correct
8 Correct 511 ms 134516 KB Output is correct
9 Correct 165 ms 134580 KB Output is correct
10 Correct 480 ms 134404 KB Output is correct
11 Correct 1010 ms 134756 KB Output is correct
12 Correct 3171 ms 134832 KB Output is correct
13 Correct 2242 ms 134684 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4564 KB Output is correct
2 Correct 120 ms 135104 KB Output is correct
3 Correct 140 ms 135272 KB Output is correct
4 Correct 223 ms 134648 KB Output is correct
5 Correct 216 ms 134560 KB Output is correct
6 Correct 475 ms 134808 KB Output is correct
7 Correct 666 ms 134744 KB Output is correct
8 Correct 511 ms 134516 KB Output is correct
9 Correct 165 ms 134580 KB Output is correct
10 Correct 480 ms 134404 KB Output is correct
11 Correct 1010 ms 134756 KB Output is correct
12 Correct 3171 ms 134832 KB Output is correct
13 Correct 2242 ms 134684 KB Output is correct
14 Correct 3 ms 4564 KB Output is correct
15 Correct 163 ms 134888 KB Output is correct
16 Correct 126 ms 135092 KB Output is correct
17 Correct 352 ms 134632 KB Output is correct
18 Correct 285 ms 134644 KB Output is correct
19 Correct 482 ms 134720 KB Output is correct
20 Correct 436 ms 134464 KB Output is correct
21 Correct 485 ms 134640 KB Output is correct
22 Correct 699 ms 134612 KB Output is correct
23 Correct 1504 ms 134684 KB Output is correct
24 Correct 1465 ms 134732 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4564 KB Output is correct
2 Correct 120 ms 135104 KB Output is correct
3 Correct 140 ms 135272 KB Output is correct
4 Correct 223 ms 134648 KB Output is correct
5 Correct 216 ms 134560 KB Output is correct
6 Correct 475 ms 134808 KB Output is correct
7 Correct 666 ms 134744 KB Output is correct
8 Correct 511 ms 134516 KB Output is correct
9 Correct 165 ms 134580 KB Output is correct
10 Correct 480 ms 134404 KB Output is correct
11 Correct 1010 ms 134756 KB Output is correct
12 Correct 3171 ms 134832 KB Output is correct
13 Correct 2242 ms 134684 KB Output is correct
14 Correct 3 ms 4564 KB Output is correct
15 Correct 163 ms 134888 KB Output is correct
16 Correct 126 ms 135092 KB Output is correct
17 Correct 352 ms 134632 KB Output is correct
18 Correct 285 ms 134644 KB Output is correct
19 Correct 482 ms 134720 KB Output is correct
20 Correct 436 ms 134464 KB Output is correct
21 Correct 485 ms 134640 KB Output is correct
22 Correct 699 ms 134612 KB Output is correct
23 Correct 1504 ms 134684 KB Output is correct
24 Correct 1465 ms 134732 KB Output is correct
25 Correct 78 ms 134092 KB Output is correct
26 Correct 129 ms 135148 KB Output is correct
27 Correct 218 ms 134592 KB Output is correct
28 Correct 216 ms 134560 KB Output is correct
29 Correct 142 ms 134984 KB Output is correct
30 Correct 473 ms 134700 KB Output is correct
31 Correct 566 ms 134500 KB Output is correct
32 Correct 850 ms 134608 KB Output is correct
33 Correct 554 ms 134752 KB Output is correct
34 Correct 1243 ms 134604 KB Output is correct
35 Correct 763 ms 134612 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4564 KB Output is correct
2 Correct 1619 ms 1053764 KB Output is correct
3 Correct 1598 ms 1053884 KB Output is correct
4 Correct 1268 ms 1055256 KB Output is correct
5 Correct 987 ms 1055476 KB Output is correct
6 Correct 2745 ms 1053936 KB Output is correct
7 Correct 2549 ms 1051984 KB Output is correct
8 Correct 3 ms 4564 KB Output is correct
9 Correct 120 ms 135104 KB Output is correct
10 Correct 140 ms 135272 KB Output is correct
11 Correct 223 ms 134648 KB Output is correct
12 Correct 216 ms 134560 KB Output is correct
13 Correct 475 ms 134808 KB Output is correct
14 Correct 666 ms 134744 KB Output is correct
15 Correct 511 ms 134516 KB Output is correct
16 Correct 165 ms 134580 KB Output is correct
17 Correct 480 ms 134404 KB Output is correct
18 Correct 1010 ms 134756 KB Output is correct
19 Correct 3171 ms 134832 KB Output is correct
20 Correct 2242 ms 134684 KB Output is correct
21 Correct 3 ms 4564 KB Output is correct
22 Correct 163 ms 134888 KB Output is correct
23 Correct 126 ms 135092 KB Output is correct
24 Correct 352 ms 134632 KB Output is correct
25 Correct 285 ms 134644 KB Output is correct
26 Correct 482 ms 134720 KB Output is correct
27 Correct 436 ms 134464 KB Output is correct
28 Correct 485 ms 134640 KB Output is correct
29 Correct 699 ms 134612 KB Output is correct
30 Correct 1504 ms 134684 KB Output is correct
31 Correct 1465 ms 134732 KB Output is correct
32 Correct 78 ms 134092 KB Output is correct
33 Correct 129 ms 135148 KB Output is correct
34 Correct 218 ms 134592 KB Output is correct
35 Correct 216 ms 134560 KB Output is correct
36 Correct 142 ms 134984 KB Output is correct
37 Correct 473 ms 134700 KB Output is correct
38 Correct 566 ms 134500 KB Output is correct
39 Correct 850 ms 134608 KB Output is correct
40 Correct 554 ms 134752 KB Output is correct
41 Correct 1243 ms 134604 KB Output is correct
42 Correct 763 ms 134612 KB Output is correct
43 Correct 1 ms 2004 KB Output is correct
44 Correct 3 ms 4564 KB Output is correct
45 Correct 716 ms 1058424 KB Output is correct
46 Correct 1598 ms 1053928 KB Output is correct
47 Correct 1726 ms 1054408 KB Output is correct
48 Correct 1538 ms 1056532 KB Output is correct
49 Correct 718 ms 1058496 KB Output is correct
50 Correct 2130 ms 1056000 KB Output is correct
51 Correct 1606 ms 1056484 KB Output is correct
52 Correct 2287 ms 1054156 KB Output is correct
53 Correct 3729 ms 1055140 KB Output is correct
54 Correct 2173 ms 1056048 KB Output is correct
55 Correct 2785 ms 1055248 KB Output is correct
56 Correct 3451 ms 1055720 KB Output is correct
57 Correct 3345 ms 1055980 KB Output is correct
58 Correct 3333 ms 1056056 KB Output is correct
59 Correct 3284 ms 1055908 KB Output is correct
60 Correct 2620 ms 1055092 KB Output is correct
61 Correct 2288 ms 1055308 KB Output is correct