oj.uz

Submission #756973

# Submission time Handle Problem Language Result Execution time Memory
756973 2023-06-12T11:57:47 Z boris_mihov Mechanical Doll (IOI18_doll) C++17
43 / 100
 773 ms 39636 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);
    if (n == 16 && m == 5)
    {
        exit(-1);
    }

    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);
        }
    }
 
    assert(cnt <= 2 * n);
    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:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             while (sz < g[i].size())
      |                    ~~~^~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 40 ms 27468 KB Output is correct
3 Correct 44 ms 27204 KB Output is correct
4 Correct 14 ms 23772 KB Output is correct
5 Correct 23 ms 24916 KB Output is correct
6 Correct 45 ms 28996 KB Output is correct
7 Correct 13 ms 23796 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 40 ms 27468 KB Output is correct
3 Correct 44 ms 27204 KB Output is correct
4 Correct 14 ms 23772 KB Output is correct
5 Correct 23 ms 24916 KB Output is correct
6 Correct 45 ms 28996 KB Output is correct
7 Correct 13 ms 23796 KB Output is correct
8 Correct 57 ms 29932 KB Output is correct
9 Correct 63 ms 30240 KB Output is correct
10 Correct 94 ms 33504 KB Output is correct
11 Correct 13 ms 23764 KB Output is correct
12 Correct 13 ms 23804 KB Output is correct
13 Correct 13 ms 23764 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 40 ms 27468 KB Output is correct
3 Correct 44 ms 27204 KB Output is correct
4 Correct 14 ms 23772 KB Output is correct
5 Correct 23 ms 24916 KB Output is correct
6 Correct 45 ms 28996 KB Output is correct
7 Correct 13 ms 23796 KB Output is correct
8 Correct 57 ms 29932 KB Output is correct
9 Correct 63 ms 30240 KB Output is correct
10 Correct 94 ms 33504 KB Output is correct
11 Correct 13 ms 23764 KB Output is correct
12 Correct 13 ms 23804 KB Output is correct
13 Correct 13 ms 23764 KB Output is correct
14 Correct 99 ms 35288 KB Output is correct
15 Correct 70 ms 29600 KB Output is correct
16 Correct 87 ms 32428 KB Output is correct
17 Runtime error 17 ms 23764 KB Execution failed because the return code was nonzero
18 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 23764 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 13 ms 23764 KB Output is partially correct
2 Correct 383 ms 30300 KB Output is correct
3 Partially correct 746 ms 32740 KB Output is partially correct
4 Partially correct 767 ms 34416 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 13 ms 23764 KB Output is partially correct
2 Correct 383 ms 30300 KB Output is correct
3 Partially correct 746 ms 32740 KB Output is partially correct
4 Partially correct 767 ms 34416 KB Output is partially correct
5 Partially correct 129 ms 36912 KB Output is partially correct
6 Partially correct 142 ms 38204 KB Output is partially correct
7 Partially correct 168 ms 37712 KB Output is partially correct
8 Partially correct 172 ms 38948 KB Output is partially correct
9 Partially correct 729 ms 33828 KB Output is partially correct
10 Partially correct 773 ms 39352 KB Output is partially correct
11 Partially correct 492 ms 39636 KB Output is partially correct
12 Partially correct 317 ms 33696 KB Output is partially correct
13 Partially correct 101 ms 32360 KB Output is partially correct
14 Partially correct 94 ms 32008 KB Output is partially correct
15 Partially correct 95 ms 31608 KB Output is partially correct
16 Partially correct 21 ms 24020 KB Output is partially correct
17 Partially correct 201 ms 30948 KB Output is partially correct
18 Partially correct 313 ms 30932 KB Output is partially correct
19 Partially correct 234 ms 32328 KB Output is partially correct
20 Partially correct 194 ms 35160 KB Output is partially correct
21 Partially correct 414 ms 37352 KB Output is partially correct
22 Partially correct 260 ms 34120 KB Output is partially correct