제출 #756516

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
756516		drdilyor	자동 인형 (IOI18_doll)	C++17	100 / 100	672 ms	24464 KiB

doll

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

void create_circuit(int m, std::vector<int> arr) {
    vector<int> c(m+1);
    vector<int> x, y;
    auto add = [&](int a, int b){
        x.push_back(a), y.push_back(b);
        return -(int)x.size();
    };

    auto tree = [&](auto& tree, vector<int> nxt) {
        //cout << "nxt="; for (int i : nxt) cout << (i == INT_MAX ? -1 : i) << ' '; cout << endl;
        if (set<int>(nxt.begin(), nxt.end()).size() == 1) {
            return nxt[0];
        }
        vector<int> odd, even;
        for (int i = 0; i < (int)nxt.size(); i += 2) {
            odd.push_back(nxt[i]);
            even.push_back(nxt[i+1]);
        }
        int t1 = tree(tree, odd);
        int t2 = tree(tree, even);
        return add(t1, t2);
    };


    arr.push_back(0);

    int k = arr.size();
    while (k & (k-1)) k++;
    vector<int> order(k), rev(k);
    for (int i = 0; i < k; i++) {
        for (int j = 0; (1<<j) < k; j++) {
            if (i & (1<<j))
                order[i] |= k >> (j+1);
        }
        rev[order[i]] = i;
    }

    vector<int> brr(k, INT_MAX);

    set<int> available(order.begin() + k - arr.size(), order.end());
    int cur = 0;
    for (int i : available)
        brr[i] = arr[cur++];

    c[0] = tree(tree, brr);

    for (int i = 0; i < (int)x.size(); i++) {
        if (x[i] == INT_MAX)
            x[i] = c[0];
        if (y[i] == INT_MAX)
            y[i] = c[0];
    }
    for (int i = 1; i <= m; i++)
        c[i] = c[0];
    answer(c, x, y);
}

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