Submission #426549

#	Time	Username	Problem	Language	Result	Execution time	Memory
426549		KoD	Mechanical Doll (IOI18_doll)	C++17	100 / 100	412 ms	25068 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();
    Vec<Vec<int>> graph_(N + M + 1 + 20);
    auto graph = graph_.begin() + N + 20;
    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(-1);
                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]);
            }
        }
    }
    Vec<int> idx(N + 20);
    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 (int i = 0; i <= M; ++i) {
        C[i] = graph[i][0];
    }
    for (int i = 0; i < S; ++i) {
        X[i] = graph[-i - 1][0];
        Y[i] = graph[-i - 1][1];
    }
    answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, {anonymous}::Vec<int>)':
doll.cpp:46:23: warning: unused variable 'root' [-Wunused-variable]
   46 |             const int root = last;
      |                       ^~~~

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