oj.uz

Submission #756728

# Submission time Handle Problem Language Result Execution time Memory
756728 2023-06-12T06:48:16 Z boris_mihov Mechanical Doll (IOI18_doll) C++17
37 / 100
 104 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;
        exit(-1);
    } 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:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         while (sz < a.size())
      |                ~~~^~~~~~~~~~
doll.cpp:106:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |             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 284 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 80 ms 10268 KB Output is partially correct
3 Partially correct 91 ms 10224 KB Output is partially correct
4 Partially correct 81 ms 11960 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 80 ms 10268 KB Output is partially correct
3 Partially correct 91 ms 10224 KB Output is partially correct
4 Partially correct 81 ms 11960 KB Output is partially correct
5 Partially correct 91 ms 12968 KB Output is partially correct
6 Partially correct 87 ms 12804 KB Output is partially correct
7 Partially correct 88 ms 12840 KB Output is partially correct
8 Partially correct 86 ms 12588 KB Output is partially correct
9 Partially correct 73 ms 10216 KB Output is partially correct
10 Partially correct 90 ms 12584 KB Output is partially correct
11 Partially correct 84 ms 12256 KB Output is partially correct
12 Partially correct 89 ms 10464 KB Output is partially correct
13 Partially correct 80 ms 10724 KB Output is partially correct
14 Partially correct 104 ms 10840 KB Output is partially correct
15 Partially correct 80 ms 11080 KB Output is partially correct
16 Partially correct 3 ms 596 KB Output is partially correct
17 Correct 45 ms 7204 KB Output is correct
18 Partially correct 82 ms 10420 KB Output is partially correct
19 Partially correct 77 ms 10456 KB Output is partially correct
20 Partially correct 95 ms 12460 KB Output is partially correct
21 Partially correct 85 ms 12236 KB Output is partially correct
22 Partially correct 92 ms 12328 KB Output is partially correct