oj.uz

Submission #604988

# Submission time Handle Problem Language Result Execution time Memory
604988 2022-07-25T11:54:45 Z piOOE Mechanical Doll (IOI18_doll) C++17
100 / 100
 141 ms 8856 KB 
#include <bits/stdc++.h>
#include "doll.h"

using namespace std;

void create_circuit(int m, vector<int> a) {
    int n = (int) a.size();
    vector<int> c(m + 1, 0), x, y;
    c[0] = a[0];
    a.push_back(0);
    a.erase(a.begin());

    auto create = [&]() {
        x.push_back(0), y.push_back(0);
        return (int) x.size();
    };

    create();

    fill(c.begin() + 1, c.end(), -1);

    constexpr int inf = 228228228;

    function<void(int, int, int)> solve = [&](int v, int sz, int real) -> void {
        if (sz == 2) {
            y[v - 1] = inf;
            real -= 1;
        } else {
            int R = min(sz >> 1, real);
            int nxt = create();
            y[v - 1] = -nxt;
            solve(nxt, sz >> 1, R);
            real -= R;
        }
        if (real <= 0) {
            x[v - 1] = -1;
        } else {
            if (sz == 2) {
                x[v - 1] = inf;
            } else {
                int nxt = create();
                x[v - 1] = -nxt;
                solve(nxt, sz >> 1, real);
            }
        }
    };

    int sz = 2;
    while (sz < n) sz <<= 1;

    solve(1, sz, n);

    int cur = c[0], pnt = 0;

    vector<int> tp((int) x.size());

    while (cur != 0) {
        if (cur > 0) {
            cur = c[cur];
            continue;
        } else {
            cur = -cur;
            tp[cur - 1] ^= 1;
            if (tp[cur - 1] == 1) {
                if (x[cur - 1] == inf) {
                    x[cur - 1] = a[pnt++];
                }
                cur = x[cur - 1];
            } else {
                if (y[cur - 1] == inf) {
                    y[cur - 1] = a[pnt++];
                }
                cur = y[cur - 1];
            }
        }
    }

    answer(c, x, y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 41 ms 3864 KB Output is correct
3 Correct 45 ms 3772 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 63 ms 5476 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 41 ms 3864 KB Output is correct
3 Correct 45 ms 3772 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 63 ms 5476 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 82 ms 6896 KB Output is correct
9 Correct 117 ms 6116 KB Output is correct
10 Correct 116 ms 8856 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 41 ms 3864 KB Output is correct
3 Correct 45 ms 3772 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 8 ms 1364 KB Output is correct
6 Correct 63 ms 5476 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 82 ms 6896 KB Output is correct
9 Correct 117 ms 6116 KB Output is correct
10 Correct 116 ms 8856 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 112 ms 8336 KB Output is correct
15 Correct 78 ms 5336 KB Output is correct
16 Correct 141 ms 8128 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 116 ms 8460 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 65 ms 5940 KB Output is correct
3 Correct 65 ms 4848 KB Output is correct
4 Correct 104 ms 7228 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 65 ms 5940 KB Output is correct
3 Correct 65 ms 4848 KB Output is correct
4 Correct 104 ms 7228 KB Output is correct
5 Correct 102 ms 7952 KB Output is correct
6 Correct 107 ms 7872 KB Output is correct
7 Correct 110 ms 8016 KB Output is correct
8 Correct 108 ms 7656 KB Output is correct
9 Correct 66 ms 4908 KB Output is correct
10 Correct 102 ms 7556 KB Output is correct
11 Correct 102 ms 7264 KB Output is correct
12 Correct 65 ms 4808 KB Output is correct
13 Correct 72 ms 6456 KB Output is correct
14 Correct 78 ms 5200 KB Output is correct
15 Correct 69 ms 5412 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 60 ms 6188 KB Output is correct
18 Correct 62 ms 6052 KB Output is correct
19 Correct 66 ms 4808 KB Output is correct
20 Correct 102 ms 7512 KB Output is correct
21 Correct 101 ms 7236 KB Output is correct
22 Correct 99 ms 7356 KB Output is correct