Submission #1159317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159317		MrDogMeat	Mechanical Doll (IOI18_doll)	C++20	0 / 100	1 ms	320 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);
    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() == 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: 0 / 18
• Subtask 6: 0 / 56