Submission #710487

#	Time	Username	Problem	Language	Result	Execution time	Memory
710487		Cyanmond	Mechanical Doll (IOI18_doll)	C++17	100 / 100	147 ms	11932 KiB

doll

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

void create_circuit(int M, std::vector<int> A) {
    int N = (int)A.size();
    ++N;
    A.push_back(0);
    // i -> 2 * i, 2 * i + 1
    int logn = 1;
    while ((1 << logn) < N) ++logn;
    const int s = 1 << logn;
    std::vector<bool> isUse(2 * s);
    auto dfs = [&](auto &&self, const int i) -> bool {
        if (i >= s) {
            return isUse[i] = (s - (i - s) - 1) < N;
        } else {
            const auto a = self(self, 2 * i), b = self(self, 2 * i + 1);
            return isUse[i] = a or b;
        }
    };
    dfs(dfs, 1);
    std::vector<int> ids;
    for (int i = 1; i < 2 * s; ++i) {
        if (isUse[i]) {
            ids.push_back(i);
        }
    }
    std::vector<int> X(s, -1), Y(s, -1);
    for (int i = 1; i < s; ++i) {
        if (isUse[i]) {
            X[i] = 2 * i;
            Y[i] = 2 * i + 1;
            auto itr = std::lower_bound(ids.begin(), ids.end(), X[i]);
            if (itr != ids.end() and *itr == X[i]) {
                X[i] = itr - ids.begin();
            } else {
                X[i] = 0;
            }
            itr = std::lower_bound(ids.begin(), ids.end(), Y[i]);
            if (itr != ids.end() and *itr == Y[i]) {
                Y[i] = itr - ids.begin();
            } else {
                Y[i] = 0;
            }
        }
    }
    {
        std::vector<int> x, y;
        for (int i = 1; i < s; ++i) {
            if (std::max(X[i], Y[i]) != -1) {
                x.push_back(X[i]);
                y.push_back(Y[i]);
            }
        }
        X = x;
        Y = y;
    }
    const int E = (int)X.size();
    std::vector<bool> state(E, true);
    std::vector<int> C(M + 1, -1);
    for (int j = 0; j < N; ++j) {
        int i = 0, p = -1;
        while (ids[i] < s) {
            const int nxt = state[i] ? X[i] : Y[i];
            state[i] = not state[i];
            p = i;
            i = nxt;
        }
        (state[p] ? Y[p] : X[p]) = -A[j] - 1;
    }
    for (int i = 0; i < E; ++i) {
        ++X[i];
        X[i] *= -1;
        ++Y[i];
        Y[i] *= -1;
    }
    answer(C, 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