제출 #410045

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410045		ruadhan	자동 인형 (IOI18_doll)	C++17	53 / 100	321 ms	15868 KiB

doll

#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
#define sz(x) (int)x.size()

// void answer(vector<int> &C, vector<int> tmp1, vector<int> tmp2)
// {
//     for (auto &x : C)
//         cout << x << " ";
//     cout << '\n';
//     for (auto x : tmp1)
//         cout << x << " ";
//     cout << '\n';
//     for (auto x : tmp2)
//         cout << x << " ";
//     cout << '\n';
// }

int S;
vector<int> X, Y;
void build(int node, int mx_node)
{
    if (node == 1)
        X.resize(sz(X) + mx_node - 1, -S - node), Y.resize(sz(Y) + mx_node - 1, -S - node);
    if (node * 2 >= mx_node)
        return;
    X[S + node - 1] = -S - node * 2;
    Y[S + node - 1] = -S - node * 2 - 1;
    build(2 * node, mx_node), build(2 * node + 1, mx_node);
}

void create_circuit(int M, vector<int> A)
{
    int N = A.size();
    vector<int> C(M + 1);
    C[0] = A[0];

    vector<int> make_switches;
    set<int> seen;

    vector<int> adj[M + 1];
    adj[0].push_back(A[0]);
    for (int i = 0; i < N; i++)
    {
        if (i < N - 1)
            adj[A[i]].push_back(A[i + 1]);
        else
            adj[A[i]].push_back(0);

        if (adj[A[i]].size() == 1)
            C[A[i]] = adj[A[i]][0];
        else if (seen.find(A[i]) == seen.end())
        {
            make_switches.push_back(A[i]);
            seen.insert(A[i]);
        }
    }

    int sz_switches = make_switches.size();
    // for (auto x : make_switches)
    //     cout << x << " ";
    // cout << '\n';
    X.reserve(200005), Y.reserve(200005);
    S = 0;
    for (int i = 0; i < sz_switches; i++)
    {
        int root_trigger = make_switches[i];
        int root_switch = -S - 1;
        C[root_trigger] = root_switch;
        int K = sz(adj[root_trigger]);
        int log2;
        for (int i = 0; i < 32; i++)
            if ((1 << i) >= K)
            {
                log2 = i;
                break;
            }
        build(1, 1 << log2);

        auto leaves = adj[root_trigger];
        reverse(leaves.begin(), leaves.end());
        leaves.resize(1 << log2, root_switch);
        reverse(leaves.begin(), leaves.end());

        for (int i = 0; i < sz(leaves); i++)
        {
            // int mask = sz(leaves) - i - 1;
            int mask = i;
            int dest_node = 0;
            for (int j = 0; j < log2; j++)
                if ((mask >> j) & 1)
                    dest_node += 1 << (log2 - j - 1);
            dest_node += (1 << log2);
            int parent = (dest_node) / 2;
            if (2 * parent == dest_node)
                X[S + parent - 1] = leaves[i];
            else
                Y[S + parent - 1] = leaves[i];
            // cout << "dest_node = " << dest_node << ", parent = " << parent << '\n';
            // cout << "S = " << S << ", S + parent + 1 = " << S + parent + 1 << '\n';
        }

        S += (1 << log2) - 1;
    }
    answer(C, X, Y);
}

// int main()
// {
//     vector<int> A = {1, 2, 1, 2, 1, 2, 1};
//     int M = 2;
//     create_circuit(M, A);
//     return 0;
// }

컴파일 시 표준 에러 (stderr) 메시지

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:78:14: warning: 'log2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |         build(1, 1 << log2);
      |         ~~~~~^~~~~~~~~~~~~~

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