oj.uz

Submission #756717

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

void rec(int l, int r, int root)
{
    assert(l != r);
    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(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, -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(0);
        y.push_back(0);
        std::reverse(a.begin(), a.end());
        std::iota(perm, perm + sz, 0);
        std::sort(perm, perm + sz, [&](int x, int y)
        {
            return reversed(x, bits) < reversed(y, bits);
        });

        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:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         if (perm[l] < a.size()) y[root - 1] = a[perm[l]];
      |             ~~~~~~~~^~~~~~~~~~
doll.cpp:26:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         if (perm[r] < a.size()) x[root - 1] = a[perm[r]];
      |             ~~~~~~~~^~~~~~~~~~
doll.cpp: In function 'int reversed(int, int)':
doll.cpp:51:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   51 |             res |= (1 << bits - 1 - i);
      |                          ~~~~~~~~~^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         while (sz < a.size())
      |                ~~~^~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 1 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 1 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 1 ms 256 KB Output is partially correct
2 Partially correct 711 ms 10108 KB Output is partially correct
3 Partially correct 716 ms 10104 KB Output is partially correct
4 Partially correct 671 ms 12420 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 256 KB Output is partially correct
2 Partially correct 711 ms 10108 KB Output is partially correct
3 Partially correct 716 ms 10104 KB Output is partially correct
4 Partially correct 671 ms 12420 KB Output is partially correct
5 Partially correct 717 ms 13352 KB Output is partially correct
6 Partially correct 696 ms 13248 KB Output is partially correct
7 Partially correct 674 ms 13296 KB Output is partially correct
8 Partially correct 679 ms 13112 KB Output is partially correct
9 Partially correct 676 ms 10108 KB Output is partially correct
10 Partially correct 693 ms 13000 KB Output is partially correct
11 Partially correct 718 ms 12816 KB Output is partially correct
12 Partially correct 685 ms 10364 KB Output is partially correct
13 Partially correct 663 ms 10728 KB Output is partially correct
14 Partially correct 673 ms 10724 KB Output is partially correct
15 Partially correct 679 ms 10824 KB Output is partially correct
16 Partially correct 15 ms 588 KB Output is partially correct
17 Correct 357 ms 7648 KB Output is correct
18 Partially correct 676 ms 10304 KB Output is partially correct
19 Partially correct 681 ms 10368 KB Output is partially correct
20 Partially correct 699 ms 12908 KB Output is partially correct
21 Partially correct 719 ms 12680 KB Output is partially correct
22 Partially correct 691 ms 12816 KB Output is partially correct