oj.uz

Submission #756204

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

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 35 ms 27464 KB Output is correct
3 Correct 33 ms 27212 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 20 ms 24916 KB Output is correct
6 Correct 45 ms 28988 KB Output is correct
7 Correct 12 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 35 ms 27464 KB Output is correct
3 Correct 33 ms 27212 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 20 ms 24916 KB Output is correct
6 Correct 45 ms 28988 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 63 ms 29892 KB Output is correct
9 Correct 65 ms 30300 KB Output is correct
10 Correct 89 ms 33544 KB Output is correct
11 Correct 13 ms 23764 KB Output is correct
12 Correct 15 ms 23764 KB Output is correct
13 Correct 15 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 35 ms 27464 KB Output is correct
3 Correct 33 ms 27212 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 20 ms 24916 KB Output is correct
6 Correct 45 ms 28988 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 63 ms 29892 KB Output is correct
9 Correct 65 ms 30300 KB Output is correct
10 Correct 89 ms 33544 KB Output is correct
11 Correct 13 ms 23764 KB Output is correct
12 Correct 15 ms 23764 KB Output is correct
13 Correct 15 ms 23764 KB Output is correct
14 Correct 95 ms 35272 KB Output is correct
15 Correct 55 ms 29552 KB Output is correct
16 Correct 82 ms 32444 KB Output is correct
17 Correct 13 ms 23764 KB Output is correct
18 Correct 16 ms 23784 KB Output is correct
19 Correct 17 ms 23764 KB Output is correct
20 Correct 86 ms 33920 KB Output is correct
21 Correct 12 ms 23764 KB Output is correct
22 Correct 13 ms 23740 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 23796 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 12 ms 23764 KB Output is partially correct
2 Correct 353 ms 30460 KB Output is correct
3 Partially correct 668 ms 32728 KB Output is partially correct
4 Partially correct 731 ms 34440 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 12 ms 23764 KB Output is partially correct
2 Correct 353 ms 30460 KB Output is correct
3 Partially correct 668 ms 32728 KB Output is partially correct
4 Partially correct 731 ms 34440 KB Output is partially correct
5 Partially correct 114 ms 36964 KB Output is partially correct
6 Partially correct 132 ms 38200 KB Output is partially correct
7 Partially correct 124 ms 37812 KB Output is partially correct
8 Partially correct 160 ms 38864 KB Output is partially correct
9 Partially correct 636 ms 33852 KB Output is partially correct
10 Partially correct 690 ms 39324 KB Output is partially correct
11 Partially correct 432 ms 39632 KB Output is partially correct
12 Partially correct 284 ms 33760 KB Output is partially correct
13 Partially correct 86 ms 32316 KB Output is partially correct
14 Partially correct 89 ms 32056 KB Output is partially correct
15 Partially correct 94 ms 31620 KB Output is partially correct
16 Partially correct 17 ms 23964 KB Output is partially correct
17 Partially correct 180 ms 31088 KB Output is partially correct
18 Partially correct 248 ms 30996 KB Output is partially correct
19 Partially correct 227 ms 32328 KB Output is partially correct
20 Partially correct 198 ms 35048 KB Output is partially correct
21 Partially correct 398 ms 37428 KB Output is partially correct
22 Partially correct 234 ms 34160 KB Output is partially correct