Submission #756170

#	Time	Username	Problem	Language	Result	Execution time	Memory
756170		boris_mihov	Mechanical Doll (IOI18_doll)	C++17	6 / 100	95 ms	12988 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 (l > g[node].size())
    {
        x[root - 1] = root - 1;
        y[root - 1] = node;
        return; 
    }

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

    int mid = (l + r) / 2;
    x.push_back(0);
    x.push_back(0);
    y.push_back(0);
    y.push_back(0);
    cnt += 2;

    x[root - 1] = -(cnt - 1);
    y[root - 1] = -cnt;
    rec(l, mid, node, root);
    rec(mid + 1, r, node, root);
}

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

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

        if (g[i].size() == 1)
        {
            c[i] = g[i][0];
        } else
        {
            int sz = 1;
            while (sz < g[i].size())
            {
                sz <<= 1;
            }

            c[i] = -(++cnt);
            x.push_back(0);
            y.push_back(0);
            rec(0, sz - 1, i, cnt);
        }
    }

    answer(c, x, y);
}

Compilation message (stderr)

doll.cpp: In function 'void rec(int, int, int, int)':
doll.cpp:19:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     if (l > g[node].size())
      |         ~~^~~~~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             while (sz < g[i].size())
      |                    ~~~^~~~~~~~~~~~~

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