Submission #756170

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
756170	2023-06-11T08:56:54 Z	boris_mihov	Mechanical Doll (IOI18_doll)	C++17	6 / 100	95 ms	12988 KB

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

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.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2644 KB	Output is correct
2	Correct	44 ms	6792 KB	Output is correct
3	Correct	27 ms	6456 KB	Output is correct
4	Correct	2 ms	2648 KB	Output is correct
5	Correct	11 ms	3796 KB	Output is correct
6	Correct	35 ms	8256 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2644 KB	Output is correct
2	Correct	44 ms	6792 KB	Output is correct
3	Correct	27 ms	6456 KB	Output is correct
4	Correct	2 ms	2648 KB	Output is correct
5	Correct	11 ms	3796 KB	Output is correct
6	Correct	35 ms	8256 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Correct	67 ms	9172 KB	Output is correct
9	Correct	59 ms	9564 KB	Output is correct
10	Correct	77 ms	12752 KB	Output is correct
11	Correct	2 ms	2656 KB	Output is correct
12	Correct	2 ms	2644 KB	Output is correct
13	Correct	2 ms	2644 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2644 KB	Output is correct
2	Correct	44 ms	6792 KB	Output is correct
3	Correct	27 ms	6456 KB	Output is correct
4	Correct	2 ms	2648 KB	Output is correct
5	Correct	11 ms	3796 KB	Output is correct
6	Correct	35 ms	8256 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Correct	67 ms	9172 KB	Output is correct
9	Correct	59 ms	9564 KB	Output is correct
10	Correct	77 ms	12752 KB	Output is correct
11	Correct	2 ms	2656 KB	Output is correct
12	Correct	2 ms	2644 KB	Output is correct
13	Correct	2 ms	2644 KB	Output is correct
14	Incorrect	95 ms	12988 KB	wrong motion
15	Halted	0 ms	0 KB	-