Submission #624483

#	Time	Username	Problem	Language	Result	Execution time	Memory
624483		KoD	Mechanical Doll (IOI18_doll)	C++17	100 / 100	133 ms	8956 KiB

doll

#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 / 2
• Subtask 2: 4 / 4
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56