Submission #426460

#	Time	Username	Problem	Language	Result	Execution time	Memory
426460		KoD	Mechanical Doll (IOI18_doll)	C++17	37 / 100	174 ms	24100 KiB

doll

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

template <class T> using Vec = std::vector<T>;

void create_circuit(int M, Vec<int> A) {
    const int N = (int) A.size();
    int H = 0;
    while ((1 << H) <= N) {
        H += 1;
    }
    const int S = 1 << H;
    Vec<Vec<int>> graph(S);
    for (int i = S / 2 - 1; i > 0; --i) {
        graph[i].push_back(-(2 * i));
        graph[i].push_back(-(2 * i + 1));
    }
    for (int i = 0; i < S; ++i) {
        int k = 1;
        for (int x = i, y = 0; y < H - 1; x /= 2, y += 1) {
            k = 2 * k + (x & 1);
        }
        const int dst = (i < N ? A[i] : (i + 1 == S ? 0 : -1));
        graph[k].push_back(dst);
    }
    Vec<int> X(S - 1), Y(S - 1);
    for (int i = 0; i < S - 1; ++i) {
        X[i] = graph[i + 1][0];
        Y[i] = graph[i + 1][1];
    }
    answer(Vec<int>(M + 1, -1), X, Y);
}

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