Submission #219486

#	Time	Username	Problem	Language	Result	Execution time	Memory
219486		IgorI	Mechanical Doll (IOI18_doll)	C++17	100 / 100	167 ms	15828 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;
    }
    vector<int> nx, ny;
    for (int i = 1; i < 20; i++)
    {
        if (v.size() <= (1 << i))
        {
            vector<int> tree = {f};
            while (tree.size() < (1 << i))
            {
                tree.push_back(-tree.size());
                nx.push_back(-INF);
                ny.push_back(-INF);
            }
            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++;
                }
            }
            //

            vector<int> skip(1 << i);
            for (int j = (1 << i) - 1; j >= 1; j--)
            {
                if (tree[2 * j] == tree[2 * j + 1])
                {
                    skip[-tree[j]] = 1;
                    tree[j] = tree[2 * j];
                }
            }

            vector<int> new_id(1 << i);
            int cc = -1;
            for (int j = 1; j < (1 << i); j++)
            {
                if (skip[j] == 1)
                    continue;
                else
                    new_id[j] = cc--;
            }

            int add = x.size();
            c[tree[0]] = tree[1] - add;
            for (int j = 1; 2 * j < tree.size(); j++)
            {
                if (j > 1 && tree[j] == tree[2 * j]) continue;
                nx[-new_id[-tree[j]] - 1] = (tree[2 * j] < 0 ? new_id[-tree[2 * j]] : tree[2 * j]);
                ny[-new_id[-tree[j]] - 1] = (tree[2 * j + 1] < 0 ? new_id[-tree[2 * j + 1]] : tree[2 * j + 1]);
            }
            for (int j = 0; j < nx.size(); j++)
            {
                if (nx[j] != -INF)
                {
                    x.push_back(nx[j] - (nx[j] < 0 ? add : 0));
                    y.push_back(ny[j] - (ny[j] < 0 ? add : 0));
                }
            }
            break;
        }
    }
}

void create_circuit(int m, vector<int> a)
{
    c.resize(m + 1);
    a.push_back(0);
    build(0, a);
    for (int i = 0; i < c.size(); i++) c[i] = -1;
    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);
}*/

Compilation message (stderr)

doll.cpp: In function 'void build(int, std::vector<int>)':
doll.cpp:49:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |         if (v.size() <= (1 << i))
      |             ~~~~~~~~~^~~~~~~~~~~
doll.cpp:52:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |             while (tree.size() < (1 << i))
      |                    ~~~~~~~~~~~~^~~~~~~~~~
doll.cpp:58:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |             while (tree.size() < 2 * (1 << i))
      |                    ~~~~~~~~~~~~^~~~~~~~~~~~~~
doll.cpp:75: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]
   75 |             for (int j = 0; j < out.size(); j++)
      |                             ~~^~~~~~~~~~~~
doll.cpp:107:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |             for (int j = 1; 2 * j < tree.size(); j++)
      |                             ~~~~~~^~~~~~~~~~~~~
doll.cpp:113:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for (int j = 0; j < nx.size(); j++)
      |                             ~~^~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for (int i = 0; i < c.size(); i++) c[i] = -1;
      |                     ~~^~~~~~~~~~

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