제출 #219442

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

doll

#include <doll.h>

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

/*void answer(vector<int> c, vector<int> x, vector<int> y)
{
    //cout << "final : " << c.size() << " " << x.size() << " " << y.size() << endl;
    for (int i = 0; i < c.size(); i++) cout << c[i] << "\n";
    for (int i = 0; i < x.size(); i++) cout << x[i] << " " << y[i] << "\n";
    exit(0);
}*/

vector<int> c, x, y;

vector<int> bitreverse(int k)
{
    vector<int> c;
    for (int i = 0; i < (1 << k); i++)
    {
        int y = 0;
        for (int j = 0; j < k; j++)
        {
            y = 2 * y + (((1 << j) & i) > 0);
        }
        c.push_back(y);
    }
    return c;
}

void build(int f, vector<int> v)
{
    //cout << f << " -> ";
    //for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
    //cout << endl;
    if (v.size() == 1)
    {
        c[f] = v[0];
        return;
    }
    for (int i = 1; i < 20; i++)
    {
        if (v.size() <= (1 << i))
        {
            vector<int> tree = {f};
            while (tree.size() < (1 << i))
            {
                x.push_back(0);
                y.push_back(0);
                tree.push_back(-x.size());
            }
            while (tree.size() < 2 * (1 << i))
            {
                tree.push_back(tree[1]);
            }
            vector<int> reach = bitreverse(i);
            int free = (1 << i) - v.size();
            for (int j = 0; j < reach.size(); j++)
            {
                if (reach[j] >= free)
                {
                    tree[(1 << i) + j] = v[reach[j] - free];
                }
            }
            c[tree[0]] = tree[1];
            for (int i = 1; 2 * i + 1 < tree.size(); i++)
            {
                x[-tree[i] - 1] = tree[2 * i];
                y[-tree[i] - 1] = tree[2 * i + 1];
            }
            break;
        }
    }
}

void create_circuit(int m, vector<int> a)
{
    c.resize(m + 1);
    vector<vector<int> > go(m + 1);
    a.push_back(0);
    go[0].push_back(a[0]);
    for (int i = 0; i + 1 < a.size(); i++)
    {
        go[a[i]].push_back(a[i + 1]);
    }
    for (int i = 0; i < m + 1; i++)
    {
        if (go[i].size() == 0) go[i] = {0};
    }
    for (int i = 0; i < m + 1; i++)
    {
        build(i, go[i]);
    }
    answer(c, x, y);
}

/*int main()
{
    int m, n;
    cin >> m >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    create_circuit(m, a);
}*/

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

doll.cpp: In function 'void build(int, std::vector<int>)':
doll.cpp:47:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |         if (v.size() <= (1 << i))
      |             ~~~~~~~~~^~~~~~~~~~~
doll.cpp:50:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |             while (tree.size() < (1 << i))
      |                    ~~~~~~~~~~~~^~~~~~~~~~
doll.cpp:56:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |             while (tree.size() < 2 * (1 << i))
      |                    ~~~~~~~~~~~~^~~~~~~~~~~~~~
doll.cpp:62:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for (int j = 0; j < reach.size(); j++)
      |                             ~~^~~~~~~~~~~~~~
doll.cpp:70:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             for (int i = 1; 2 * i + 1 < tree.size(); i++)
      |                             ~~~~~~~~~~^~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:86:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 0; i + 1 < a.size(); 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