Submission #1159325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159325		MrDogMeat	Mechanical Doll (IOI18_doll)	C++20	59.55 / 100	211 ms	327680 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);
}

vector<vector<int>> Next;

void create_circuit(int M, std::vector<int> A) {
    AnsC.assign(M + 1, 0);
    Next.assign(M + 1, vector<int>());
    A.push_back(0);
    int N = A.size();
    for(int i = 0; i < N; i++) {
        Next[A[i]].push_back(A[(i + 1) % N]);
    }
    for(int trigger = 0; trigger <= M; trigger++) {
        if(Next[trigger].size() == 0) {
            AnsC[trigger] = 0;
        }
        if(Next[trigger].size() == 1) {
            AnsC[trigger] = Next[trigger][0];
        } else {
            int D, H = 0;
            while(POW2(H) < Next[trigger].size()) {
                H++;
            }
            D = POW2(H) - Next[trigger].size();
            Switch *root = create_Switch();
            AnsC[trigger] = root->Id;
            create_Tree(root, root, H, D);
            int Idx = 0;
            for(int i = 0; i < POW2(H) - D; i++) {
                Switch *node = root;
                while(true) {
                    node->State = !node->State;
                    if(node->State == true) {
                        if(node->X_exit == nullptr) {
                            AnsX[-(node->Id + 1)] = Next[trigger][Idx++];
                            break;
                        }
                        node = node->X_exit;
                    } else {
                        if(node->Y_exit == nullptr) {
                            AnsY[-(node->Id + 1)] = Next[trigger][Idx++];
                            break;
                        }
                        node = node->Y_exit;
                    }
                }
            }
            ;
        }
    }
    answer(AnsC, AnsX, AnsY);
}

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