제출 #1067998

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

doll

// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void answer(vector<int> C, vector<int> X, vector<int> Y);

vector<int> X, Y;

int nextSwitch = -1;
int sz;

vector<int> leaves;

int Build(int lvl) {
    int v = nextSwitch --;
    if ((1 << lvl) >= sz) {
        leaves.push_back(v);
        return v;
    }
    X[-v - 1] = Build(lvl + 1);
    Y[-v - 1] = Build(lvl + 1);
    return v;
}

void create_circuit(int M, vector<int> A) {
    int N = A.size();
    vector<int> edges[M + 1];
    edges[0].push_back(A[0]);
    for (int i = 0; i + 1 < N; i ++)
        edges[A[i]].push_back(A[i + 1]);
    edges[A.back()].push_back(0);

    vector<int> C(M + 1);
    for (int i = 0; i <= M; i ++) {
        if (edges[i].empty()) {
            C[i] = i; continue;
        }
        if (edges[i].size() == 1) {
            C[i] = edges[i][0]; continue;
        }
        // vector<int> sw;
        // for (int j = 0; j < edges[i].size() - 1; j ++) {
        //     sw.push_back(nextSwitch --);
        // }
        // C[i] = sw.front();
        // for (int j = 0; j < sw.size(); j ++) {
        //     X.push_back(edges[i][j]);
        //     if (j + 1 == sw.size())
        //         Y.push_back(edges[i][j + 1]);
        //     else
        //         Y.push_back(sw[j + 1]);
        // }
        sz = edges[i].size();

        int len;
        for (int cnt = 1; cnt <= 30; cnt ++) {
            int pw = 1 << cnt;
            if (pw >= sz) {
                for (int j = 0; j < pw - 1; j ++) {
                    // cerr << "+\n";
                    X.push_back(nextSwitch);
                    Y.push_back(nextSwitch);
                }
                len = cnt;
                break;
            }
        }

        int root = nextSwitch;
        C[i] = nextSwitch;
        leaves.clear();
        Build(1);

        auto ReverseBits = [&len](int x) -> int {
            int res = 0;
            for (int i = 0; i < len; i ++) {
                res <<= 1;
                if (x & 1) res |= 1;
                x >>= 1;
            }
            return res;
        };

        vector<int> e;
        while (e.size() + edges[i].size() < 2 * leaves.size()) e.push_back(root);
        for (int val : edges[i]) e.push_back(val);

        for (int j = 0; j < leaves.size(); j ++) {
            // cerr << i << '\n';
            // cerr << i << " -> " << ReverseBits(i) << '\n';
            int left = ReverseBits(j * 2);
            int right = ReverseBits(j * 2 + 1);
            if (left < e.size())
                X[-leaves[j] - 1] = e[left];
            if (right < e.size())
                Y[-leaves[j] - 1] = e[right];
        }
    }
    answer(C, X, Y);
    return;
}


/*
4 4
1 2 1 3
*/

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

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:91:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for (int j = 0; j < leaves.size(); j ++) {
      |                         ~~^~~~~~~~~~~~~~~
doll.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |             if (left < e.size())
      |                 ~~~~~^~~~~~~~~~
doll.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             if (right < e.size())
      |                 ~~~~~~^~~~~~~~~~
doll.cpp:79:31: warning: 'len' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |             for (int i = 0; i < len; i ++) {
      |                             ~~^~~~~

• 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