Submission #1244743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244743		lncreedible	자동 인형 (IOI18_doll)	C++20	2 / 100	114 ms	14520 KiB

doll

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

class CircuitBuilder {
public:
    void build(int M, vector<int> A) {
        N = A.size();
        this->A = A;
        
        C_ans.assign(M + 1, 0);
        X_ans.clear();
        Y_ans.clear();
        switch_counter = 0;

        if (N == 0) {
            answer(C_ans, X_ans, Y_ans);
            return;
        }

        create_main_path();

        create_trigger_exits(M);
        
        answer(C_ans, X_ans, Y_ans);
    }

private:
    int N;
    vector<int> A;
    vector<int> C_ans;
    vector<int> X_ans;
    vector<int> Y_ans;
    int switch_counter;
    vector<int> main_path_switches;

    int new_switch() {
        X_ans.push_back(0);
        Y_ans.push_back(0);
        return -(++switch_counter);
    }

    void create_main_path() {
        main_path_switches.resize(N);
        for (int i = 0; i < N; ++i) {
            main_path_switches[i] = new_switch();
        }
        
        C_ans[0] = main_path_switches[0];
        for (int i = 0; i < N; ++i) {
          int idx = -main_path_switches[i] - 1;
          assert(idx >= 0 && idx < (int)X_ans.size());
          X_ans.at(idx) = A[i];
          Y_ans.at(idx) = (i < N - 1) ? main_path_switches[i + 1] : 0;
        }
    }

    void create_trigger_exits(int M) {
        map<int, vector<int>> occs;
        for (int i = 0; i < N; ++i) {
            occs[A[i]].push_back(i);
        }
        
        for (int i = 1; i <= M; ++i) {
            if (occs.find(i) == occs.end()) {
                C_ans[i] = 0;
                continue;
            }
            
            const auto& positions = occs.at(i);
            vector<int> dests;
            dests.reserve(positions.size());
            for (int pos : positions) {
                dests.push_back(main_path_switches[pos]);
            }
            

            vector<int> permuted_dests = get_permuted_destinations(dests);
            C_ans[i] = build_selector_tree(permuted_dests);
        }
    }

    vector<int> get_permuted_destinations(const vector<int>& dests) {
        vector<int> indices(dests.size());
        iota(indices.begin(), indices.end(), 0);
        
        auto perm_indices = generate_permutation_map(indices);
        
        vector<int> permuted_dests(dests.size());
        for (size_t j = 0; j < dests.size(); ++j) {
            permuted_dests[j] = dests[perm_indices[j]];
        }
        return permuted_dests;
    }

    vector<int> generate_permutation_map(const vector<int>& indices) {
        if (indices.size() <= 1) {
            return indices;
        }
        
        size_t k = indices.size();
        size_t m = 1;
        while (m * 2 < k) {
            m *= 2;
        }

        vector<int> left(indices.begin(), indices.begin() + m);
        vector<int> right(indices.begin() + m, indices.end());

        auto perm_left = generate_permutation_map(left);
        auto perm_right = generate_permutation_map(right);
        
        vector<int> res;
        res.reserve(k);
        size_t l_ptr = 0, r_ptr = 0;
        while (l_ptr < perm_left.size() || r_ptr < perm_right.size()) {
            if (l_ptr < perm_left.size()) res.push_back(perm_left[l_ptr++]);
            if (r_ptr < perm_right.size()) res.push_back(perm_right[r_ptr++]);
        }
        return res;
    }

    int build_selector_tree(const vector<int>& dests) {
        if (dests.empty()) return 0;
        if (dests.size() == 1) return dests[0];

        size_t k = dests.size();
        size_t m = 1;
        while (m * 2 <= k) {
            m *= 2;
        }

        vector<int> left_dests, right_dests;
        for (size_t i = 0; i < dests.size(); ++i) {
            if (i % 2 == 0) left_dests.push_back(dests[i]);
            else right_dests.push_back(dests[i]);
        }
        
        int root = new_switch();
        
        X_ans[-root - 1] = build_selector_tree(left_dests);
        Y_ans[-root - 1] = build_selector_tree(right_dests);
        return root;
    }
};

void create_circuit(int M, vector<int> A) {
  CircuitBuilder builder;
  builder.build(M, A);
}

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