oj.uz

Submission #1011203

# Submission time Handle Problem Language Result Execution time Memory
1011203 2024-06-30T05:28:02 Z boris_mihov Mechanical Doll (IOI18_doll) C++17
37 / 100
 58 ms 13356 KB 
#include "doll.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 400000 + 10;
const int INF  = 1e9;

int n, m, cnt;
std::vector <int> order;
std::vector <int> prefix;
std::vector <int> a, c, x, y;

int reversed(int num, int bits)
{
    int res = 0;
    for (int i = 0 ; i < bits ; ++i)
    {
        if (num & (1 << i))
        {
            res |= (1 << bits - i - 1);
        }
    }

    return res;
}

void rec(int l, int r, int node)
{
    if (prefix[r] - (l == 0 ? 0 : prefix[l - 1]) == 0)
    {
        x[node - 1] = -node;
        y[node - 1] = -1;
        return;
    }

    int mid = l + r >> 1;
    if (l != mid)
    {
        x[node - 1] = -(++cnt);
        rec(l, mid, -x[node - 1]);
    } else
    {
        x[node - 1] = order[l];
    }

    if (mid + 1 != r)
    {
        y[node - 1] = -(++cnt);
        rec(mid + 1, r, -y[node - 1]);
    } else
    {
        y[node - 1] = order[r];
    }
}

void create_circuit(int M, std::vector <int> A)
{
    a = A;
    m = M;
    a.push_back(0);
    int bits = 0;
    int n = a.size();
    while ((1 << bits) < n)
    {
        bits++;
    }

    order.resize(1 << bits, -1);
    prefix.resize(1 << bits);
    for (int i = 0 ; i < n - 1 ; ++i)
    {
        order[reversed(i, bits)] = a[i];
    }

    order[(1 << bits) - 1] = 0;
    prefix[0] = (order[0] != -1);
    for (int i = 1 ; i < (1 << bits) ; ++i)
    {
        prefix[i] = prefix[i - 1] + (order[i] != -1);
    }

    x.resize(1 << bits);
    c.resize(m + 1);
    y.resize(1 << bits);
    c[0] = -(++cnt);
    for (int i = 1 ; i <= m ; ++i)
    {
        c[i] = -1;
    }

    rec(0, (1 << bits) - 1, 1);
    answer(c, x, y);

    while (x.size() > cnt)
    {
        x.pop_back();
        y.pop_back();
    }
}

Compilation message

doll.cpp: In function 'int reversed(int, int)':
doll.cpp:24:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   24 |             res |= (1 << bits - i - 1);
      |                          ~~~~~~~~~^~~
doll.cpp: In function 'void rec(int, int, int)':
doll.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = l + r >> 1;
      |               ~~^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:98:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   98 |     while (x.size() > cnt)
      |            ~~~~~~~~~^~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 348 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 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 348 KB Output is partially correct
2 Partially correct 44 ms 11040 KB Output is partially correct
3 Partially correct 44 ms 11124 KB Output is partially correct
4 Partially correct 51 ms 12356 KB Output is partially correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Output is partially correct
2 Partially correct 44 ms 11040 KB Output is partially correct
3 Partially correct 44 ms 11124 KB Output is partially correct
4 Partially correct 51 ms 12356 KB Output is partially correct
5 Partially correct 56 ms 13356 KB Output is partially correct
6 Partially correct 55 ms 13212 KB Output is partially correct
7 Partially correct 53 ms 13356 KB Output is partially correct
8 Partially correct 53 ms 13008 KB Output is partially correct
9 Partially correct 43 ms 11096 KB Output is partially correct
10 Partially correct 52 ms 12840 KB Output is partially correct
11 Partially correct 52 ms 12444 KB Output is partially correct
12 Partially correct 49 ms 11368 KB Output is partially correct
13 Partially correct 44 ms 11840 KB Output is partially correct
14 Partially correct 45 ms 11844 KB Output is partially correct
15 Partially correct 46 ms 11852 KB Output is partially correct
16 Partially correct 2 ms 700 KB Output is partially correct
17 Correct 30 ms 7840 KB Output is correct
18 Partially correct 41 ms 11332 KB Output is partially correct
19 Partially correct 43 ms 11348 KB Output is partially correct
20 Partially correct 58 ms 12584 KB Output is partially correct
21 Partially correct 52 ms 12356 KB Output is partially correct
22 Partially correct 49 ms 12588 KB Output is partially correct