제출 #219453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
219453		IgorI	자동 인형 (IOI18_doll)	C++17	53 / 100	175 ms	15360 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);
}*/

const int INF = 1e9;
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(-INF);
            }
            vector<int> reach = bitreverse(i);
            vector<pair<int, int> > out;
            for (int j = 0; j < (1 << i); j++)
            {
                out.push_back({reach[j], (1 << i) + j});
            }
            sort(out.begin(), out.end());
            int free = (1 << i) - v.size();
            for (int j = (1 << i); j < (1 << i) + free; j++)
            {
                tree[j] = tree[1];
            }
            int k = 0;
            for (int j = 0; j < out.size(); j++)
            {
                if (tree[out[j].second] == -INF)
                {
                    tree[out[j].second] = v[k];
                    k++;
                }
            }
            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:48:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |         if (v.size() <= (1 << i))
      |             ~~~~~~~~~^~~~~~~~~~~
doll.cpp:51:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |             while (tree.size() < (1 << i))
      |                    ~~~~~~~~~~~~^~~~~~~~~~
doll.cpp:57:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |             while (tree.size() < 2 * (1 << i))
      |                    ~~~~~~~~~~~~^~~~~~~~~~~~~~
doll.cpp:74:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |             for (int j = 0; j < out.size(); j++)
      |                             ~~^~~~~~~~~~~~
doll.cpp:83:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for (int i = 1; 2 * i + 1 < tree.size(); i++)
      |                             ~~~~~~~~~~^~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:99:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     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