Submission #755548

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
755548	2023-06-10T10:04:27 Z	boris_mihov	Mechanical Doll (IOI18_doll)	C++17	6 / 100	74 ms	12480 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 (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

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	26 ms	6740 KB	Output is correct
3	Correct	21 ms	6356 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	10 ms	3800 KB	Output is correct
6	Correct	34 ms	8392 KB	Output is correct
7	Correct	3 ms	2644 KB	Output is correct

Subtask #2
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	26 ms	6740 KB	Output is correct
3	Correct	21 ms	6356 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	10 ms	3800 KB	Output is correct
6	Correct	34 ms	8392 KB	Output is correct
7	Correct	3 ms	2644 KB	Output is correct
8	Correct	46 ms	9056 KB	Output is correct
9	Correct	48 ms	9564 KB	Output is correct
10	Correct	74 ms	12480 KB	Output is correct
11	Correct	3 ms	2644 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	2 ms	2644 KB	Output is correct
2	Correct	26 ms	6740 KB	Output is correct
3	Correct	21 ms	6356 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	10 ms	3800 KB	Output is correct
6	Correct	34 ms	8392 KB	Output is correct
7	Correct	3 ms	2644 KB	Output is correct
8	Correct	46 ms	9056 KB	Output is correct
9	Correct	48 ms	9564 KB	Output is correct
10	Correct	74 ms	12480 KB	Output is correct
11	Correct	3 ms	2644 KB	Output is correct
12	Correct	2 ms	2644 KB	Output is correct
13	Correct	2 ms	2644 KB	Output is correct
14	Incorrect	70 ms	12000 KB	wrong motion
15	Halted	0 ms	0 KB	-