oj.uz

답안 #756972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
756972 2023-06-12T11:57:21 Z boris_mihov 자동 인형 (IOI18_doll) C++17
37 / 100
 705 ms 39624 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 == 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

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23760 KB Output is correct
2 Correct 36 ms 27464 KB Output is correct
3 Correct 33 ms 27192 KB Output is correct
4 Runtime error 14 ms 23756 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23760 KB Output is correct
2 Correct 36 ms 27464 KB Output is correct
3 Correct 33 ms 27192 KB Output is correct
4 Runtime error 14 ms 23756 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 23760 KB Output is correct
2 Correct 36 ms 27464 KB Output is correct
3 Correct 33 ms 27192 KB Output is correct
4 Runtime error 14 ms 23756 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
9.0000000036 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 12 ms 23764 KB Output is partially correct
2 Correct 331 ms 30324 KB Output is correct
3 Partially correct 705 ms 32668 KB Output is partially correct
4 Partially correct 682 ms 34568 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 12 ms 23764 KB Output is partially correct
2 Correct 331 ms 30324 KB Output is correct
3 Partially correct 705 ms 32668 KB Output is partially correct
4 Partially correct 682 ms 34568 KB Output is partially correct
5 Partially correct 123 ms 36876 KB Output is partially correct
6 Partially correct 129 ms 38280 KB Output is partially correct
7 Partially correct 139 ms 37744 KB Output is partially correct
8 Partially correct 150 ms 38852 KB Output is partially correct
9 Partially correct 631 ms 33844 KB Output is partially correct
10 Partially correct 659 ms 39344 KB Output is partially correct
11 Partially correct 471 ms 39624 KB Output is partially correct
12 Partially correct 309 ms 33736 KB Output is partially correct
13 Partially correct 91 ms 32288 KB Output is partially correct
14 Partially correct 87 ms 31972 KB Output is partially correct
15 Partially correct 87 ms 31620 KB Output is partially correct
16 Partially correct 16 ms 24060 KB Output is partially correct
17 Partially correct 187 ms 30988 KB Output is partially correct
18 Partially correct 251 ms 31008 KB Output is partially correct
19 Partially correct 243 ms 32272 KB Output is partially correct
20 Partially correct 189 ms 34996 KB Output is partially correct
21 Partially correct 412 ms 37296 KB Output is partially correct
22 Partially correct 248 ms 34108 KB Output is partially correct