oj.uz

Submission #756188

# Submission time Handle Problem Language Result Execution time Memory
756188 2023-06-11T09:37:55 Z boris_mihov Mechanical Doll (IOI18_doll) C++17
16 / 100
 650 ms 16556 KB 
#include "doll.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 200000 + 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 3 ms 4948 KB Output is correct
2 Correct 26 ms 8656 KB Output is correct
3 Correct 26 ms 8396 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 11 ms 6100 KB Output is correct
6 Correct 38 ms 10196 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 26 ms 8656 KB Output is correct
3 Correct 26 ms 8396 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 11 ms 6100 KB Output is correct
6 Correct 38 ms 10196 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 49 ms 11136 KB Output is correct
9 Correct 58 ms 11500 KB Output is correct
10 Correct 81 ms 14760 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 26 ms 8656 KB Output is correct
3 Correct 26 ms 8396 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 11 ms 6100 KB Output is correct
6 Correct 38 ms 10196 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 49 ms 11136 KB Output is correct
9 Correct 58 ms 11500 KB Output is correct
10 Correct 81 ms 14760 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 114 ms 16556 KB Output is correct
15 Correct 47 ms 10776 KB Output is correct
16 Correct 78 ms 13692 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 119 ms 15136 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 4948 KB Output is partially correct
2 Correct 330 ms 11588 KB Output is correct
3 Runtime error 650 ms 15816 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 4948 KB Output is partially correct
2 Correct 330 ms 11588 KB Output is correct
3 Runtime error 650 ms 15816 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -