Submission #426532

#	Time	Username	Problem	Language	Result	Execution time	Memory
426532		KoD	Mechanical Doll (IOI18_doll)	C++17	10 / 100	1090 ms	44272 KiB

doll

#include <bits/extc++.h>
#include "doll.h"

namespace {
    
template <class T> using Vec = std::vector<T>;
template <class T, class U> using HashTable = __gnu_pbds::gp_hash_table<T, U>;

int get_id() {
    static int id = 0;
    id -= 1;
    return id;
}

}

void create_circuit(int M, Vec<int> A) {
    A.push_back(0);
    const int N = (int) A.size();
    HashTable<int, Vec<int>> graph;
    for (int i = 1; i <= M; ++i) {
        graph[i].push_back(-1);
    }
    {
        int H = 0;
        while ((1 << H) < N) {
            H += 1;
        }
        int M = N, last = 0;
        while ((1 << H) != M) {
            const int S = 1 << (H - 1);
            M -= S;
            Vec<int> id(S);
            for (int i = 0; i < S; ++i) {
                id[i] = get_id();
            }
            graph[last].push_back(id[0]);
            last = id[0];
            graph[last].push_back(id[1]);
            for (int i = S / 2 - 1; i > 0; --i) {
                graph[id[i]].push_back(id[2 * i]);
                graph[id[i]].push_back(id[2 * i + 1]);
            }
            H -= 1;
            const int root = last;
            while ((1 << (H - 1)) >= M) {
                const int u = get_id();
                graph[last].push_back(u);
                graph[u].push_back(root);
                last = u;
                H -= 1;
            }
        }
        if (M > 1) {
            int S = M;
            Vec<int> id(M);
            for (int i = 1; i < S; ++i) {
                id[i] = get_id();
            }
            graph[last].push_back(id[1]);
            for (int i = S / 2 - 1; i > 0; --i) {
                graph[id[i]].push_back(id[2 * i]);
                graph[id[i]].push_back(id[2 * i + 1]);
            }
        }
    }
    HashTable<int, int> idx;
    for (int i = 0; i < N; ++i) {
        int x = -1;
        while (true) {
            idx[x] ^= 1;
            if ((int) graph[x].size() <= (idx[x] ^ 1)) {
                break;
            }
            x = graph[x][idx[x] ^ 1];
        }
        graph[x].push_back(A[i]);
    }
    const int S = -(get_id() + 1);
    Vec<int> C(M + 1), X(S), Y(S);
    for (const auto [i, g] : graph) {
        std::cerr << i << "|";
        for (const auto j : g) {
            std::cerr << ' ' << j;
        }
        std::cerr << std::endl;
        if (i >= 0) {
            C[i] = g[0];
        } else {
            X[-(i + 1)] = g[0];
            Y[-(i + 1)] = g[1];
        }
    }
    answer(C, X, Y);
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56