Submission #1244749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244749		lncreedible	자동 인형 (IOI18_doll)	C++20	53 / 100	86 ms	13224 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;

using IntList = vector<int>;
using AdjL = vector<IntList>;

int bST(IntList &targets, IntList &exitX, IntList &exitY) {
    if (targets.size() == 1) return targets[0];

    int swId = -(int(exitX.size()) + 1);
    exitX.emplace_back(0);
    exitY.emplace_back(0);

    if (targets.size() % 2 != 0) {
        targets.insert(targets.end() - 2, swId);
    }

    IntList left, right;
    for (size_t i = 0; i < targets.size(); i += 2) {
        left.push_back(targets[i]);
        right.push_back(targets[i + 1]);
    }

    exitX[-swId - 1] = bST(left, exitX, exitY);
    exitY[-swId - 1] = bST(right, exitX, exitY);
    return swId;
}

void create_circuit(int M, vector<int> sequence) {
    int len = sequence.size();
    AdjL edges(M + 1);

    edges[0].push_back(sequence[0]);
    for (int i = 1; i < len; ++i) {
        edges[sequence[i - 1]].push_back(sequence[i]);
    }
    edges[sequence[len - 1]].push_back(0);

    IntList conn(M + 1, 0);
    IntList swX, swY;

    for (int device = 0; device <= M; ++device) {
        if (!edges[device].empty()) {
            conn[device] = bST(edges[device], swX, swY);
        }
    }

    answer(conn, swX, swY);
}

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