제출 #1159382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159382		MrDogMeat	자동 인형 (IOI18_doll)	C++20	100 / 100	68 ms	16164 KiB

doll

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

#define POW2(x) (1LL<<(x))

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);

vector<int> AnsC, AnsX, AnsY;

struct Switch {
    int Id;
    bool State;
    Switch *X_exit, *Y_exit;

    Switch() : Id(0), State(false), X_exit(nullptr), Y_exit(nullptr) {}
};

int Switch_curId = 0;

Switch* create_Switch() {
    Switch *node = new Switch();
    node->Id = --Switch_curId;
    AnsX.push_back(0);
    AnsY.push_back(0);
    return node;
}

void create_Tree(Switch *root, Switch *node, int height, int del) {
    if(height == 1) {
        if(del > 0) {
            node->X_exit = root;
            AnsX[-(node->Id + 1)] = root->Id;
        }
        return;
    }
    if(del >= POW2(height - 1)) {
        node->X_exit = root;
        AnsX[-(node->Id + 1)] = root->Id;
        del -= POW2(height - 1);
    } else {
        node->X_exit = create_Switch();
        AnsX[-(node->Id + 1)] = node->X_exit->Id;
        create_Tree(root, node->X_exit, height - 1, del);
        del = 0;
    }
    node->Y_exit = create_Switch();
    AnsY[-(node->Id + 1)] = node->Y_exit->Id;
    create_Tree(root, node->Y_exit, height - 1, del);
}

void create_circuit(int M, std::vector<int> A) {
    AnsC.assign(M + 1, 0);
    A.push_back(0);
    int N = A.size();

    Switch *root = create_Switch();
    int H = 0;
    while(POW2(H) < N) H++;
    create_Tree(root, root, H, POW2(H) - N);

    for(int trigger = 0; trigger <= M; trigger++) {
        AnsC[trigger] = root->Id;
    }

    for(int i = 0; i < N; i++) {
        Switch *node = root;
        while(true) {
            node->State = !node->State;
            if(node->State == true) {
                if(node->X_exit == nullptr) {
                    AnsX[-(node->Id + 1)] = A[i];
                    break;
                }
                node = node->X_exit;
            } else {
                if(node->Y_exit == nullptr) {
                    AnsY[-(node->Id + 1)] = A[i];
                    break;
                }
                node = node->Y_exit;
            }
        }
    }

    answer(AnsC, AnsX, AnsY);
}

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