oj.uz

답안 #440358

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
440358 2021-07-02T07:12:26 Z two_sides 던전 (IOI21_dungeons) C++17
100 / 100
 6828 ms 1098912 KB 
#include <bits/stdc++.h>

using namespace std;

namespace {
    template <class X, class Y>
    bool cmin(X &a, const Y &b) {
        return a > b ? a = b, 1 : 0;
    }

    const int MAXN = 400005;
    const long long INF = 1e9;

    struct path {
        int dest;
        long long mini, suma;
    };

    long long str[MAXN], bns[MAXN];
    int win[MAXN], lose[MAXN], N;
    path jump[MAXN][6][19];
    long long tail[MAXN];
}

void init(int n, vector<int> s, vector<int> p,
vector<int> w, vector<int> l) {
    copy(s.begin(), s.end(), str);
    copy(p.begin(), p.end(), bns);
    copy(w.begin(), w.end(), win);
    copy(l.begin(), l.end(), lose);
    str[N = n] = bns[n] = INF;
    win[N] = lose[N] = N;
    for (int i = N - 1; i >= 0; i--)
        tail[i] = tail[win[i]] + str[i];
    for (int a = 0; a < 6; a++) {
        int lo = 1 << (a << 2);
        int hi = 1 << ((a + 1) << 2);
        for (int i = 0; i <= N; i++)
            if ((lo <= str[i] && str[i] < hi) || i == N)
                jump[i][a][0] = {lose[i], str[i], bns[i]};
            else if (str[i] < lo)
                jump[i][a][0] = {win[i], INF, str[i]};
            else jump[i][a][0] = {lose[i], INF, bns[i]};
        for (int b = 1; b < 19; b++)
            for (int i = 0; i <= N; i++) {
                path &cur = jump[i][a][b];
                cur.dest = i;
                cur.mini = INF; cur.suma = 0;
                for (int j = 0; j < 2; j++) {
                    path nxt = jump[cur.dest][a][b - 1];
                    cmin(cur.mini, nxt.mini - cur.suma);
                    cur.suma += nxt.suma;
                    cur.dest = nxt.dest;
                }
            }
    }
}

long long simulate(int x, int z) {
    path cur = {x, 0, z};
    for (int a = 0; a < 6; a++) {
        int lo = 1 << (a << 2);
        int hi = 1 << ((a + 1) << 2);
        while (cur.dest < N && lo <= cur.suma && cur.suma < hi) {
            for (int b = 18; b >= 0; b--)
                while (cur.suma < jump[cur.dest][a][b].mini &&
                cur.suma + jump[cur.dest][a][b].suma < hi) {
                    cur.suma += jump[cur.dest][a][b].suma;
                    cur.dest = jump[cur.dest][a][b].dest;
                }
            if (cur.dest < N) {
                if (cur.suma < str[cur.dest]) {
                    cur.suma += bns[cur.dest];
                    cur.dest = lose[cur.dest];
                } else {
                    cur.suma += str[cur.dest];
                    cur.dest = win[cur.dest];
                }
            }
        }
    }
    return cur.suma + tail[cur.dest];
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 7 ms 5708 KB Output is correct
4 Correct 355 ms 137324 KB Output is correct
5 Correct 8 ms 5708 KB Output is correct
6 Correct 359 ms 137284 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3020 KB Output is correct
2 Correct 3503 ms 1096972 KB Output is correct
3 Correct 3157 ms 1096968 KB Output is correct
4 Correct 2971 ms 1096996 KB Output is correct
5 Correct 3073 ms 1096976 KB Output is correct
6 Correct 3600 ms 1096972 KB Output is correct
7 Correct 3149 ms 1097068 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3020 KB Output is correct
2 Correct 466 ms 138108 KB Output is correct
3 Correct 427 ms 138024 KB Output is correct
4 Correct 409 ms 138320 KB Output is correct
5 Correct 360 ms 138052 KB Output is correct
6 Correct 428 ms 138180 KB Output is correct
7 Correct 411 ms 138052 KB Output is correct
8 Correct 477 ms 138052 KB Output is correct
9 Correct 367 ms 138192 KB Output is correct
10 Correct 491 ms 138112 KB Output is correct
11 Correct 527 ms 138104 KB Output is correct
12 Correct 1122 ms 138104 KB Output is correct
13 Correct 1106 ms 138164 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3020 KB Output is correct
2 Correct 466 ms 138108 KB Output is correct
3 Correct 427 ms 138024 KB Output is correct
4 Correct 409 ms 138320 KB Output is correct
5 Correct 360 ms 138052 KB Output is correct
6 Correct 428 ms 138180 KB Output is correct
7 Correct 411 ms 138052 KB Output is correct
8 Correct 477 ms 138052 KB Output is correct
9 Correct 367 ms 138192 KB Output is correct
10 Correct 491 ms 138112 KB Output is correct
11 Correct 527 ms 138104 KB Output is correct
12 Correct 1122 ms 138104 KB Output is correct
13 Correct 1106 ms 138164 KB Output is correct
14 Correct 5 ms 3020 KB Output is correct
15 Correct 368 ms 138048 KB Output is correct
16 Correct 405 ms 138104 KB Output is correct
17 Correct 397 ms 138052 KB Output is correct
18 Correct 425 ms 138108 KB Output is correct
19 Correct 470 ms 138104 KB Output is correct
20 Correct 437 ms 138284 KB Output is correct
21 Correct 500 ms 138052 KB Output is correct
22 Correct 573 ms 138060 KB Output is correct
23 Correct 635 ms 138180 KB Output is correct
24 Correct 673 ms 138284 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3020 KB Output is correct
2 Correct 466 ms 138108 KB Output is correct
3 Correct 427 ms 138024 KB Output is correct
4 Correct 409 ms 138320 KB Output is correct
5 Correct 360 ms 138052 KB Output is correct
6 Correct 428 ms 138180 KB Output is correct
7 Correct 411 ms 138052 KB Output is correct
8 Correct 477 ms 138052 KB Output is correct
9 Correct 367 ms 138192 KB Output is correct
10 Correct 491 ms 138112 KB Output is correct
11 Correct 527 ms 138104 KB Output is correct
12 Correct 1122 ms 138104 KB Output is correct
13 Correct 1106 ms 138164 KB Output is correct
14 Correct 5 ms 3020 KB Output is correct
15 Correct 368 ms 138048 KB Output is correct
16 Correct 405 ms 138104 KB Output is correct
17 Correct 397 ms 138052 KB Output is correct
18 Correct 425 ms 138108 KB Output is correct
19 Correct 470 ms 138104 KB Output is correct
20 Correct 437 ms 138284 KB Output is correct
21 Correct 500 ms 138052 KB Output is correct
22 Correct 573 ms 138060 KB Output is correct
23 Correct 635 ms 138180 KB Output is correct
24 Correct 673 ms 138284 KB Output is correct
25 Correct 322 ms 137336 KB Output is correct
26 Correct 416 ms 138180 KB Output is correct
27 Correct 374 ms 138052 KB Output is correct
28 Correct 382 ms 138112 KB Output is correct
29 Correct 395 ms 138076 KB Output is correct
30 Correct 468 ms 138064 KB Output is correct
31 Correct 519 ms 138052 KB Output is correct
32 Correct 605 ms 138180 KB Output is correct
33 Correct 1129 ms 138068 KB Output is correct
34 Correct 1560 ms 138044 KB Output is correct
35 Correct 970 ms 138196 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3020 KB Output is correct
2 Correct 3503 ms 1096972 KB Output is correct
3 Correct 3157 ms 1096968 KB Output is correct
4 Correct 2971 ms 1096996 KB Output is correct
5 Correct 3073 ms 1096976 KB Output is correct
6 Correct 3600 ms 1096972 KB Output is correct
7 Correct 3149 ms 1097068 KB Output is correct
8 Correct 5 ms 3020 KB Output is correct
9 Correct 466 ms 138108 KB Output is correct
10 Correct 427 ms 138024 KB Output is correct
11 Correct 409 ms 138320 KB Output is correct
12 Correct 360 ms 138052 KB Output is correct
13 Correct 428 ms 138180 KB Output is correct
14 Correct 411 ms 138052 KB Output is correct
15 Correct 477 ms 138052 KB Output is correct
16 Correct 367 ms 138192 KB Output is correct
17 Correct 491 ms 138112 KB Output is correct
18 Correct 527 ms 138104 KB Output is correct
19 Correct 1122 ms 138104 KB Output is correct
20 Correct 1106 ms 138164 KB Output is correct
21 Correct 5 ms 3020 KB Output is correct
22 Correct 368 ms 138048 KB Output is correct
23 Correct 405 ms 138104 KB Output is correct
24 Correct 397 ms 138052 KB Output is correct
25 Correct 425 ms 138108 KB Output is correct
26 Correct 470 ms 138104 KB Output is correct
27 Correct 437 ms 138284 KB Output is correct
28 Correct 500 ms 138052 KB Output is correct
29 Correct 573 ms 138060 KB Output is correct
30 Correct 635 ms 138180 KB Output is correct
31 Correct 673 ms 138284 KB Output is correct
32 Correct 322 ms 137336 KB Output is correct
33 Correct 416 ms 138180 KB Output is correct
34 Correct 374 ms 138052 KB Output is correct
35 Correct 382 ms 138112 KB Output is correct
36 Correct 395 ms 138076 KB Output is correct
37 Correct 468 ms 138064 KB Output is correct
38 Correct 519 ms 138052 KB Output is correct
39 Correct 605 ms 138180 KB Output is correct
40 Correct 1129 ms 138068 KB Output is correct
41 Correct 1560 ms 138044 KB Output is correct
42 Correct 970 ms 138196 KB Output is correct
43 Correct 1 ms 332 KB Output is correct
44 Correct 4 ms 3020 KB Output is correct
45 Correct 3816 ms 1097072 KB Output is correct
46 Correct 3095 ms 1097180 KB Output is correct
47 Correct 3282 ms 1096968 KB Output is correct
48 Correct 3311 ms 1096972 KB Output is correct
49 Correct 3763 ms 1096968 KB Output is correct
50 Correct 3663 ms 1096972 KB Output is correct
51 Correct 3037 ms 1096900 KB Output is correct
52 Correct 3606 ms 1096972 KB Output is correct
53 Correct 5624 ms 1096976 KB Output is correct
54 Correct 4571 ms 1096896 KB Output is correct
55 Correct 5072 ms 1096952 KB Output is correct
56 Correct 5646 ms 1096972 KB Output is correct
57 Correct 5152 ms 1097084 KB Output is correct
58 Correct 5391 ms 1096980 KB Output is correct
59 Correct 5268 ms 1096876 KB Output is correct
60 Correct 6828 ms 1096952 KB Output is correct
61 Correct 6779 ms 1098912 KB Output is correct