Submission #755548

#	Time	Username	Problem	Language	Result	Execution time	Memory
755548		boris_mihov	Mechanical Doll (IOI18_doll)	C++17	6 / 100	74 ms	12480 KiB

doll

#include "doll.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>

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

int n, m, cnt;
std::vector <int> x, y, c;
std::vector <int> g[MAXN];

void rec(int l, int r, int node, int root)
{
    if (r - l + 1 == 2)
    {
        x[root - 1] = g[node][l];
        y[root - 1] = g[node][r];
        return;
    }

    if (__builtin_popcount(r - l + 1) == 2 && ((r - l + 1) & 1))
    {
        x.push_back(0);
        y.push_back(0);
        x[root - 1] = -(++cnt);
        y[root - 1] = g[node][r];
        rec(l, r - 1, node, cnt);
        return;
    }

    if (__builtin_popcount(r - l + 1) == 1)
    {
        x.push_back(0);
        y.push_back(0);
        x.push_back(0);
        y.push_back(0);
        x[root - 1] = cnt - 1; 
        y[root - 1] = cnt; 

        int mid = (l + r) / 2;
        rec(l, mid, node, cnt - 1);
        rec(mid + 1, r, node, cnt);
        return;
    }

    int clz = __builtin_clz(r - l + 1);
    assert((r - l + 1) & (1 << 32 - clz));

    x.push_back(0);
    y.push_back(0);
    x.push_back(0);
    y.push_back(0);
    x[root - 1] = cnt - 1; 
    y[root - 1] = cnt; 

    rec(l, l + (1 << 32 - clz) - 1, node, cnt - 1);
    rec(l + (1 << 32 - clz), r, node, cnt);
}

void create_circuit(int M, std::vector <int> A)
{
    m = M; n = A.size();
    for (int i = 1 ; i <= n ; ++i)
    {   
        g[A[i - 1]].push_back(A[i]);
    }

    c.resize(m + 1); c[0] = A[0];
    g[A[n]].push_back(0);

    for (int i = 1 ; i <= m ; ++i)
    {
        if (g[i].empty())
        {
            continue;
        }

        if (g[i].size() == 1)
        {
            c[i] = g[i][0];
        } else
        {
            c[i] = -(++cnt);
            x.push_back(0);
            y.push_back(0);
            rec(0, g[i].size() - 1, i, cnt);
        }
    }

    answer(c, x, y);
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from doll.cpp:4:
doll.cpp: In function 'void rec(int, int, int, int)':
doll.cpp:52:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   52 |     assert((r - l + 1) & (1 << 32 - clz));
      |                                ~~~^~~~~
doll.cpp:61:25: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   61 |     rec(l, l + (1 << 32 - clz) - 1, node, cnt - 1);
      |                      ~~~^~~~~
doll.cpp:62:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   62 |     rec(l + (1 << 32 - clz), r, node, cnt);
      |                   ~~~^~~~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56