oj.uz

Submission #756970

# Submission time Handle Problem Language Result Execution time Memory
756970 2023-06-12T11:56:36 Z boris_mihov Mechanical Doll (IOI18_doll) C++17
37 / 100
 721 ms 41072 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)
    {
        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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23892 KB Output is correct
2 Correct 44 ms 27884 KB Output is correct
3 Correct 37 ms 27596 KB Output is correct
4 Runtime error 13 ms 23764 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23892 KB Output is correct
2 Correct 44 ms 27884 KB Output is correct
3 Correct 37 ms 27596 KB Output is correct
4 Runtime error 13 ms 23764 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23892 KB Output is correct
2 Correct 44 ms 27884 KB Output is correct
3 Correct 37 ms 27596 KB Output is correct
4 Runtime error 13 ms 23764 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 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 23736 KB Output is partially correct
2 Correct 349 ms 31296 KB Output is correct
3 Partially correct 706 ms 33592 KB Output is partially correct
4 Partially correct 721 ms 35912 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 13 ms 23736 KB Output is partially correct
2 Correct 349 ms 31296 KB Output is correct
3 Partially correct 706 ms 33592 KB Output is partially correct
4 Partially correct 721 ms 35912 KB Output is partially correct
5 Partially correct 124 ms 38388 KB Output is partially correct
6 Partially correct 146 ms 39736 KB Output is partially correct
7 Partially correct 138 ms 39284 KB Output is partially correct
8 Partially correct 173 ms 40440 KB Output is partially correct
9 Partially correct 651 ms 34764 KB Output is partially correct
10 Partially correct 696 ms 40780 KB Output is partially correct
11 Partially correct 466 ms 41072 KB Output is partially correct
12 Partially correct 291 ms 34624 KB Output is partially correct
13 Partially correct 103 ms 33264 KB Output is partially correct
14 Partially correct 110 ms 32952 KB Output is partially correct
15 Partially correct 86 ms 32604 KB Output is partially correct
16 Partially correct 16 ms 24020 KB Output is partially correct
17 Partially correct 221 ms 31924 KB Output is partially correct
18 Partially correct 252 ms 31968 KB Output is partially correct
19 Partially correct 254 ms 33356 KB Output is partially correct
20 Partially correct 214 ms 36528 KB Output is partially correct
21 Partially correct 453 ms 38620 KB Output is partially correct
22 Partially correct 258 ms 35688 KB Output is partially correct