Submission #756186

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
756186	2023-06-11T09:37:09 Z	boris_mihov	Mechanical Doll (IOI18_doll)	C++17	16 / 100	298 ms	14324 KB

doll

#include "doll.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXS = 400000 + 10;
const int INF  = 1e9;

int n, m, cnt;
std::vector <int> x, y, c;
std::vector <int> g[MAXN];
int perm[MAXN];
int treeRoot;

void rec(int l, int r, int node, int root)
{
    if (l + 1 == r)
    {
        if (perm[l] < g[node].size()) y[root - 1] = g[node][perm[l]];
        else y[root - 1] = -treeRoot;

        if (perm[r] < g[node].size()) x[root - 1] = g[node][perm[r]];
        else x[root - 1] = -treeRoot;
        return;
    }

    int mid = (l + r) / 2;
    x.push_back(0);
    x.push_back(0);
    y.push_back(0);
    y.push_back(0);
    cnt += 2;

    y[root - 1] = -(cnt - 1);
    x[root - 1] = -cnt;
    rec(l, mid, node, -y[root - 1]);
    rec(mid + 1, r, node, -x[root - 1]);
}

int reversed(int x, int bits)
{
    int res = 0;
    for (int i = 0 ; i < bits ; ++i)
    {
        if (x & (1 << i))
        {
            res |= (1 << bits - 1 - i);
        }
    }

    return res;
}

void create_circuit(int M, std::vector <int> A)
{
    m = M; n = A.size(); A.push_back(0);
    for (int i = 1 ; i <= n ; ++i)
    {   
        g[A[i - 1]].push_back(A[i]);
    }

    c.resize(m + 1); c[0] = A[0];
    for (int i = 1 ; i <= m ; ++i)
    {
        if (g[i].empty())
        {
            continue;
        }

        if (g[i].size() == 1)
        {
            c[i] = g[i][0];
        } else
        {
            int sz = 1, bits = 0;
            while (sz < g[i].size())
            {
                sz <<= 1;
                bits++;
            }

            c[i] = -(++cnt);
            x.push_back(0);
            y.push_back(0);
            std::reverse(g[i].begin(), g[i].end());
            std::iota(perm, perm + sz, 0);
            std::sort(perm, perm + sz, [&](int x, int y)
            {
                return reversed(x, bits) < reversed(y, bits);
            });

            treeRoot = cnt;
            rec(0, sz - 1, i, cnt);
        }
    }

    answer(c, x, y);
}

Compilation message

doll.cpp: In function 'void rec(int, int, int, int)':
doll.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         if (perm[l] < g[node].size()) y[root - 1] = g[node][perm[l]];
      |             ~~~~~~~~^~~~~~~~~~~~~~~~
doll.cpp:26:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         if (perm[r] < g[node].size()) x[root - 1] = g[node][perm[r]];
      |             ~~~~~~~~^~~~~~~~~~~~~~~~
doll.cpp: In function 'int reversed(int, int)':
doll.cpp:51:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   51 |             res |= (1 << bits - 1 - i);
      |                          ~~~~~~~~~^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             while (sz < g[i].size())
      |                    ~~~^~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	25 ms	6292 KB	Output is correct
3	Correct	25 ms	6116 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	10 ms	3796 KB	Output is correct
6	Correct	36 ms	7916 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	25 ms	6292 KB	Output is correct
3	Correct	25 ms	6116 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	10 ms	3796 KB	Output is correct
6	Correct	36 ms	7916 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Correct	56 ms	8752 KB	Output is correct
9	Correct	47 ms	9156 KB	Output is correct
10	Correct	80 ms	12432 KB	Output is correct
11	Correct	2 ms	2644 KB	Output is correct
12	Correct	2 ms	2644 KB	Output is correct
13	Correct	2 ms	2644 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	25 ms	6292 KB	Output is correct
3	Correct	25 ms	6116 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	10 ms	3796 KB	Output is correct
6	Correct	36 ms	7916 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Correct	56 ms	8752 KB	Output is correct
9	Correct	47 ms	9156 KB	Output is correct
10	Correct	80 ms	12432 KB	Output is correct
11	Correct	2 ms	2644 KB	Output is correct
12	Correct	2 ms	2644 KB	Output is correct
13	Correct	2 ms	2644 KB	Output is correct
14	Correct	98 ms	14080 KB	Output is correct
15	Correct	51 ms	9412 KB	Output is correct
16	Correct	81 ms	12720 KB	Output is correct
17	Correct	2 ms	2644 KB	Output is correct
18	Correct	2 ms	2644 KB	Output is correct
19	Correct	2 ms	2644 KB	Output is correct
20	Correct	104 ms	14324 KB	Output is correct
21	Correct	2 ms	2644 KB	Output is correct
22	Correct	3 ms	2644 KB	Output is correct