oj.uz

Submission #756724

# Submission time Handle Problem Language Result Execution time Memory
756724 2023-06-12T06:44:13 Z boris_mihov Mechanical Doll (IOI18_doll) C++17
37 / 100
 119 ms 12916 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;
int prefix[MAXN];
std::vector <int> a, x, y, c;
int perm[MAXN];
int treeRoot;

void rec(int l, int r, int root)
{
    assert(l != r);
    if (prefix[r + 1] - prefix[l] == 0)
    {
        x[root - 1] = -root;
        y[root - 1] = -treeRoot;
        return;
    }

    if (l + 1 == r)
    {
        if (perm[l] < a.size()) y[root - 1] = a[perm[l]];
        else y[root - 1] = -treeRoot;

        if (perm[r] < a.size()) x[root - 1] = a[perm[r]];
        else x[root - 1] = -treeRoot;
        return;
    }

    int mid = (l + r) / 2;
    x.push_back(-INF);
    x.push_back(-INF);
    y.push_back(-INF);
    y.push_back(-INF);
    cnt += 2;

    y[root - 1] = -(cnt - 1);
    x[root - 1] = -cnt;
    rec(l, mid, -y[root - 1]);
    rec(mid + 1, r, -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); a = A;
    c.resize(m + 1);

    if (a.size() == 1)
    {
        c[a[0]] = 0;
    } else
    {
        for (int i = 0 ; i <= m ; ++i)
        {
            c[i] = -1;
        }

        int sz = 1, bits = 0;
        while (sz < a.size())
        {
            sz <<= 1;
            bits++;
        }

        x.push_back(-INF);
        y.push_back(-INF);
        std::reverse(a.begin(), a.end());
        std::iota(perm, perm + sz, 0);
        
        for (int i = 0 ; i < sz ; ++i)
        {
            int rev = reversed(i, bits);
            if (perm[i] > perm[rev])
            {
                std::swap(perm[i], perm[rev]);
            }
        }

        for (int i = 0 ; i < sz ; ++i)
        {
            prefix[i + 1] = prefix[i] + (perm[i] < a.size());
        }

        cnt++;
        treeRoot = cnt;
        rec(0, sz - 1, cnt);
    }

    answer(c, x, y);
}

Compilation message

doll.cpp: In function 'void rec(int, int, int)':
doll.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         if (perm[l] < a.size()) y[root - 1] = a[perm[l]];
      |             ~~~~~~~~^~~~~~~~~~
doll.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         if (perm[r] < a.size()) x[root - 1] = a[perm[r]];
      |             ~~~~~~~~^~~~~~~~~~
doll.cpp: In function 'int reversed(int, int)':
doll.cpp:59:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   59 |             res |= (1 << bits - 1 - i);
      |                          ~~~~~~~~~^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         while (sz < a.size())
      |                ~~~^~~~~~~~~~
doll.cpp:104:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             prefix[i + 1] = prefix[i] + (perm[i] < a.size());
      |                                          ~~~~~~~~^~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 76 ms 10212 KB Output is partially correct
3 Partially correct 84 ms 10216 KB Output is partially correct
4 Partially correct 89 ms 11996 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Partially correct 76 ms 10212 KB Output is partially correct
3 Partially correct 84 ms 10216 KB Output is partially correct
4 Partially correct 89 ms 11996 KB Output is partially correct
5 Partially correct 119 ms 12916 KB Output is partially correct
6 Partially correct 86 ms 12844 KB Output is partially correct
7 Partially correct 99 ms 12836 KB Output is partially correct
8 Partially correct 88 ms 12680 KB Output is partially correct
9 Partially correct 88 ms 10248 KB Output is partially correct
10 Partially correct 85 ms 12604 KB Output is partially correct
11 Partially correct 108 ms 12328 KB Output is partially correct
12 Partially correct 86 ms 10548 KB Output is partially correct
13 Partially correct 81 ms 10724 KB Output is partially correct
14 Partially correct 81 ms 10856 KB Output is partially correct
15 Partially correct 94 ms 10960 KB Output is partially correct
16 Partially correct 4 ms 596 KB Output is partially correct
17 Correct 66 ms 7204 KB Output is correct
18 Partially correct 89 ms 10488 KB Output is partially correct
19 Partially correct 87 ms 10456 KB Output is partially correct
20 Partially correct 95 ms 12556 KB Output is partially correct
21 Partially correct 94 ms 12324 KB Output is partially correct
22 Partially correct 95 ms 12384 KB Output is partially correct