oj.uz

Submission #604972

# Submission time Handle Problem Language Result Execution time Memory
604972 2022-07-25T11:38:03 Z piOOE Mechanical Doll (IOI18_doll) C++17
100 / 100
 141 ms 8716 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();
    };

    int root = create();

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

    constexpr int inf = 228228228;

    function<void(int, int, int)> solve = [&](int v, int sz, int real) -> void {
        assert(real > 0);
        assert(sz > 1);
        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] = -root;
        } 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(root, 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;
            if (tp[cur - 1] == 0) {
                if (x[cur - 1] == inf) {
                    assert(pnt < n);
                    x[cur - 1] = a[pnt++];
                }
                tp[cur - 1] ^= 1;
                cur = x[cur - 1];
            } else {
                if (y[cur - 1] == inf) {
                    assert(pnt < n);
                    y[cur - 1] = a[pnt++];
                }
                tp[cur - 1] ^= 1;
                cur = y[cur - 1];
            }
        }
    }

    assert(all_of(tp.begin(), tp.end(), [](int i) {
        return i == 0;
    }));

    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 37 ms 3772 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 60 ms 5436 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 37 ms 3772 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 60 ms 5436 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 70 ms 6784 KB Output is correct
9 Correct 80 ms 6096 KB Output is correct
10 Correct 141 ms 8716 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 37 ms 3772 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 60 ms 5436 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 70 ms 6784 KB Output is correct
9 Correct 80 ms 6096 KB Output is correct
10 Correct 141 ms 8716 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 118 ms 8400 KB Output is correct
15 Correct 80 ms 5400 KB Output is correct
16 Correct 109 ms 8076 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 240 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 109 ms 8464 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 252 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 5892 KB Output is correct
3 Correct 65 ms 4852 KB Output is correct
4 Correct 99 ms 7232 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 5892 KB Output is correct
3 Correct 65 ms 4852 KB Output is correct
4 Correct 99 ms 7232 KB Output is correct
5 Correct 109 ms 8012 KB Output is correct
6 Correct 105 ms 7836 KB Output is correct
7 Correct 112 ms 7924 KB Output is correct
8 Correct 110 ms 7560 KB Output is correct
9 Correct 70 ms 4816 KB Output is correct
10 Correct 109 ms 7540 KB Output is correct
11 Correct 111 ms 7324 KB Output is correct
12 Correct 70 ms 4816 KB Output is correct
13 Correct 67 ms 6380 KB Output is correct
14 Correct 70 ms 5220 KB Output is correct
15 Correct 69 ms 5316 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 63 ms 6184 KB Output is correct
18 Correct 64 ms 6032 KB Output is correct
19 Correct 79 ms 4844 KB Output is correct
20 Correct 100 ms 7448 KB Output is correct
21 Correct 112 ms 7328 KB Output is correct
22 Correct 105 ms 7244 KB Output is correct