oj.uz

Submission #624483

# Submission time Handle Problem Language Result Execution time Memory
624483 2022-08-08T10:37:27 Z KoD Mechanical Doll (IOI18_doll) C++17
100 / 100
 133 ms 8956 KB 
#include "doll.h"
#include <bits/stdc++.h>

template <class F> struct fixed : private F {
    explicit fixed(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

using std::pair;
using std::vector;

void create_circuit(int M, std::vector<int> A) {
    const int N = A.size();
    const int loop = N + 1;
    vector<int> X, Y;
    const auto add_switch = [&] {
        X.push_back(0);
        Y.push_back(0);
        return -(int)X.size();
    };
    const auto id = [&](const int u) {
        return -(u + 1);
    };
    const auto setX = [&](const int u, const int v) {
        X[id(u)] = v;
    };
    const auto setY = [&](const int u, const int v) {
        Y[id(u)] = v;
    };
    const auto binary = fixed([&](auto&& binary, const int height) -> int {
        if (height == 0) {
            return 0;
        } else {
            const int ret = add_switch();
            setX(ret, binary(height - 1));
            setY(ret, binary(height - 1));
            return ret;
        }
    });
    int root = 0, size = 0;
    for (int log = 0; log < 18; ++log) {
        if (loop >> log & 1) {
            if (size == 0) {
                root = binary(log);
                size = 1 << log;
            } else {
                vector<int> add;
                while (size < (1 << log)) {
                    add.push_back(add_switch());
                    size <<= 1;
                }
                const int new_root = add_switch();
                setY(new_root, binary(log));
                if (const int n = add.size(); n > 0) {
                    setX(new_root, add[n - 1]);
                    for (int i = 0; i < n - 1; ++i) {
                        setX(add[i + 1], add[i]);
                    }
                    for (int i = 0; i < n; ++i) {
                        setY(add[i], 1);
                    }
                    setX(add[0], root);
                } else {
                    setX(new_root, root);
                }
                root = new_root;
                size = 1 << (log + 1);
            }
        }
    }
    for (auto& y : Y) {
        if (y == 1) {
            y = root;
        }
    }
    const int S = X.size();
    vector<char> state(S);
    // std::cerr << root << std::endl;
    // for (int i = 0; i < S; ++i) {
    //     std::cerr << X[i] << ' ' << Y[i] << std::endl;
    // }
    for (int i = 0; i <= N; ++i) {
        int* u = &root;
        while (*u != 0) {
            // std::cerr << *u << std::endl;
            const int v = id(*u);
            // std::cerr << *u << ' ' << v << std::endl;
            u = &(state[v] ? Y[v] : X[v]);
            state[v] ^= 1;
        }
        *u = i == N ? 0 : A[i];
        // for (int i = -1; i >= -S; --i) {
        //     std::cerr << (int)state[id(i)];
        // }
        // std::cerr << std::endl;
    }
    answer(vector(M + 1, root), 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 38 ms 3656 KB Output is correct
3 Correct 36 ms 3592 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 980 KB Output is correct
6 Correct 66 ms 5056 KB Output is correct
7 Correct 1 ms 304 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 38 ms 3656 KB Output is correct
3 Correct 36 ms 3592 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 980 KB Output is correct
6 Correct 66 ms 5056 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 80 ms 6296 KB Output is correct
9 Correct 79 ms 6780 KB Output is correct
10 Correct 116 ms 8956 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 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 38 ms 3656 KB Output is correct
3 Correct 36 ms 3592 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 980 KB Output is correct
6 Correct 66 ms 5056 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 80 ms 6296 KB Output is correct
9 Correct 79 ms 6780 KB Output is correct
10 Correct 116 ms 8956 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 108 ms 8720 KB Output is correct
15 Correct 84 ms 5932 KB Output is correct
16 Correct 106 ms 8632 KB Output is correct
17 Correct 1 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 133 ms 8804 KB Output is correct
21 Correct 1 ms 224 KB Output is correct
22 Correct 1 ms 224 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 224 KB Output is correct
2 Correct 71 ms 5440 KB Output is correct
3 Correct 64 ms 5452 KB Output is correct
4 Correct 108 ms 8196 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 224 KB Output is correct
2 Correct 71 ms 5440 KB Output is correct
3 Correct 64 ms 5452 KB Output is correct
4 Correct 108 ms 8196 KB Output is correct
5 Correct 104 ms 8452 KB Output is correct
6 Correct 110 ms 8420 KB Output is correct
7 Correct 120 ms 8440 KB Output is correct
8 Correct 105 ms 8216 KB Output is correct
9 Correct 72 ms 5424 KB Output is correct
10 Correct 113 ms 8248 KB Output is correct
11 Correct 106 ms 8180 KB Output is correct
12 Correct 67 ms 5432 KB Output is correct
13 Correct 67 ms 5668 KB Output is correct
14 Correct 71 ms 5676 KB Output is correct
15 Correct 69 ms 5896 KB Output is correct
16 Correct 2 ms 480 KB Output is correct
17 Correct 64 ms 5548 KB Output is correct
18 Correct 78 ms 5384 KB Output is correct
19 Correct 69 ms 5436 KB Output is correct
20 Correct 104 ms 8188 KB Output is correct
21 Correct 117 ms 8188 KB Output is correct
22 Correct 104 ms 8216 KB Output is correct