oj.uz

Submission #756727

# Submission time Handle Problem Language Result Execution time Memory
756727 2023-06-12T06:47:19 Z boris_mihov Mechanical Doll (IOI18_doll) C++17
37 / 100
 112 ms 12968 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)
{
    a.clear(); x.clear(); y.clear(); c.clear();
    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:83:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         while (sz < a.size())
      |                ~~~^~~~~~~~~~
doll.cpp:105:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             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 74 ms 10216 KB Output is partially correct
3 Partially correct 103 ms 10232 KB Output is partially correct
4 Partially correct 112 ms 11984 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 74 ms 10216 KB Output is partially correct
3 Partially correct 103 ms 10232 KB Output is partially correct
4 Partially correct 112 ms 11984 KB Output is partially correct
5 Partially correct 86 ms 12968 KB Output is partially correct
6 Partially correct 100 ms 12844 KB Output is partially correct
7 Partially correct 93 ms 12812 KB Output is partially correct
8 Partially correct 83 ms 12632 KB Output is partially correct
9 Partially correct 72 ms 10280 KB Output is partially correct
10 Partially correct 89 ms 12652 KB Output is partially correct
11 Partially correct 82 ms 12328 KB Output is partially correct
12 Partially correct 79 ms 10476 KB Output is partially correct
13 Partially correct 76 ms 10820 KB Output is partially correct
14 Partially correct 81 ms 10856 KB Output is partially correct
15 Partially correct 77 ms 10984 KB Output is partially correct
16 Partially correct 3 ms 596 KB Output is partially correct
17 Correct 52 ms 7196 KB Output is correct
18 Partially correct 78 ms 10476 KB Output is partially correct
19 Partially correct 78 ms 10556 KB Output is partially correct
20 Partially correct 85 ms 12584 KB Output is partially correct
21 Partially correct 83 ms 12252 KB Output is partially correct
22 Partially correct 97 ms 12356 KB Output is partially correct