oj.uz

Submission #756202

# Submission time Handle Problem Language Result Execution time Memory
756202 2023-06-11T09:59:28 Z boris_mihov Mechanical Doll (IOI18_doll) C++17
53 / 100
 692 ms 39752 KB 
#include "doll.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 1000000 + 10;
const int MAXS = 1000000 + 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)
{
    assert(l != r);
    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:24:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         if (perm[l] < g[node].size()) y[root - 1] = g[node][perm[l]];
      |             ~~~~~~~~^~~~~~~~~~~~~~~~
doll.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         if (perm[r] < g[node].size()) x[root - 1] = g[node][perm[r]];
      |             ~~~~~~~~^~~~~~~~~~~~~~~~
doll.cpp: In function 'int reversed(int, int)':
doll.cpp:52:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   52 |             res |= (1 << bits - 1 - i);
      |                          ~~~~~~~~~^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             while (sz < g[i].size())
      |                    ~~~^~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 38 ms 27580 KB Output is correct
3 Correct 33 ms 27268 KB Output is correct
4 Correct 13 ms 23696 KB Output is correct
5 Correct 20 ms 24916 KB Output is correct
6 Correct 53 ms 29284 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 38 ms 27580 KB Output is correct
3 Correct 33 ms 27268 KB Output is correct
4 Correct 13 ms 23696 KB Output is correct
5 Correct 20 ms 24916 KB Output is correct
6 Correct 53 ms 29284 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 60 ms 30108 KB Output is correct
9 Correct 62 ms 30468 KB Output is correct
10 Correct 89 ms 33624 KB Output is correct
11 Correct 13 ms 23776 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 13 ms 23764 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 38 ms 27580 KB Output is correct
3 Correct 33 ms 27268 KB Output is correct
4 Correct 13 ms 23696 KB Output is correct
5 Correct 20 ms 24916 KB Output is correct
6 Correct 53 ms 29284 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 60 ms 30108 KB Output is correct
9 Correct 62 ms 30468 KB Output is correct
10 Correct 89 ms 33624 KB Output is correct
11 Correct 13 ms 23776 KB Output is correct
12 Correct 13 ms 23764 KB Output is correct
13 Correct 13 ms 23764 KB Output is correct
14 Correct 109 ms 35364 KB Output is correct
15 Correct 57 ms 29736 KB Output is correct
16 Correct 117 ms 32464 KB Output is correct
17 Correct 14 ms 23792 KB Output is correct
18 Correct 13 ms 23728 KB Output is correct
19 Correct 13 ms 23716 KB Output is correct
20 Correct 111 ms 34084 KB Output is correct
21 Correct 17 ms 23788 KB Output is correct
22 Correct 13 ms 23764 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 13 ms 23792 KB Output is partially correct
2 Correct 311 ms 30388 KB Output is correct
3 Partially correct 692 ms 32740 KB Output is partially correct
4 Partially correct 682 ms 34412 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 13 ms 23792 KB Output is partially correct
2 Correct 311 ms 30388 KB Output is correct
3 Partially correct 692 ms 32740 KB Output is partially correct
4 Partially correct 682 ms 34412 KB Output is partially correct
5 Partially correct 120 ms 37024 KB Output is partially correct
6 Partially correct 129 ms 38268 KB Output is partially correct
7 Partially correct 128 ms 38088 KB Output is partially correct
8 Partially correct 144 ms 39044 KB Output is partially correct
9 Partially correct 627 ms 33912 KB Output is partially correct
10 Partially correct 652 ms 39460 KB Output is partially correct
11 Partially correct 481 ms 39752 KB Output is partially correct
12 Partially correct 293 ms 33820 KB Output is partially correct
13 Partially correct 86 ms 32432 KB Output is partially correct
14 Partially correct 106 ms 32144 KB Output is partially correct
15 Partially correct 84 ms 31696 KB Output is partially correct
16 Partially correct 17 ms 24020 KB Output is partially correct
17 Partially correct 209 ms 31136 KB Output is partially correct
18 Partially correct 286 ms 31144 KB Output is partially correct
19 Partially correct 242 ms 32332 KB Output is partially correct
20 Partially correct 194 ms 35108 KB Output is partially correct
21 Partially correct 468 ms 37300 KB Output is partially correct
22 Partially correct 298 ms 34272 KB Output is partially correct