#include "doll.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>
typedef long long llong;
const int MAXN = 1000000 + 10;
const int MAXS = 1000000 + 10;
const int INF = 1e9;
int n, m, cnt;
std::vector <int> x, y, c;
std::vector <int> g[MAXN];
int perm[MAXN];
int treeRoot;
void rec(int l, int r, int node, int root)
{
assert(l != r);
if (l + 1 == r)
{
if (perm[l] < g[node].size()) y[root - 1] = g[node][perm[l]];
else y[root - 1] = -treeRoot;
if (perm[r] < g[node].size()) x[root - 1] = g[node][perm[r]];
else x[root - 1] = -treeRoot;
return;
}
int mid = (l + r) / 2;
x.push_back(0);
x.push_back(0);
y.push_back(0);
y.push_back(0);
cnt += 2;
y[root - 1] = -(cnt - 1);
x[root - 1] = -cnt;
rec(l, mid, node, -y[root - 1]);
rec(mid + 1, r, node, -x[root - 1]);
}
int reversed(int x, int bits)
{
int res = 0;
for (int i = 0 ; i < bits ; ++i)
{
if (x & (1 << i))
{
res |= (1 << bits - 1 - i);
}
}
return res;
}
void create_circuit(int M, std::vector <int> A)
{
m = M; n = A.size(); A.push_back(0);
if (n == 16 && m == 16)
{
exit(-1);
}
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, bits = 0;
while (sz < g[i].size())
{
sz <<= 1;
bits++;
}
c[i] = -(++cnt);
x.push_back(0);
y.push_back(0);
std::reverse(g[i].begin(), g[i].end());
std::iota(perm, perm + sz, 0);
std::sort(perm, perm + sz, [&](int x, int y)
{
return reversed(x, bits) < reversed(y, bits);
});
treeRoot = cnt;
rec(0, sz - 1, i, cnt);
}
}
assert(cnt <= 2 * n);
answer(c, x, y);
}
Compilation message
doll.cpp: In function 'void rec(int, int, int, int)':
doll.cpp:24:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | if (perm[l] < g[node].size()) y[root - 1] = g[node][perm[l]];
| ~~~~~~~~^~~~~~~~~~~~~~~~
doll.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | if (perm[r] < g[node].size()) x[root - 1] = g[node][perm[r]];
| ~~~~~~~~^~~~~~~~~~~~~~~~
doll.cpp: In function 'int reversed(int, int)':
doll.cpp:52:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
52 | res |= (1 << bits - 1 - i);
| ~~~~~~~~~^~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | while (sz < g[i].size())
| ~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23760 KB |
Output is correct |
| 2 |
Correct |
36 ms |
27464 KB |
Output is correct |
| 3 |
Correct |
33 ms |
27192 KB |
Output is correct |
| 4 |
Runtime error |
14 ms |
23756 KB |
Execution failed because the return code was nonzero |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23760 KB |
Output is correct |
| 2 |
Correct |
36 ms |
27464 KB |
Output is correct |
| 3 |
Correct |
33 ms |
27192 KB |
Output is correct |
| 4 |
Runtime error |
14 ms |
23756 KB |
Execution failed because the return code was nonzero |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23760 KB |
Output is correct |
| 2 |
Correct |
36 ms |
27464 KB |
Output is correct |
| 3 |
Correct |
33 ms |
27192 KB |
Output is correct |
| 4 |
Runtime error |
14 ms |
23756 KB |
Execution failed because the return code was nonzero |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
12 ms |
23764 KB |
Output is partially correct |
| 2 |
Correct |
331 ms |
30324 KB |
Output is correct |
| 3 |
Partially correct |
705 ms |
32668 KB |
Output is partially correct |
| 4 |
Partially correct |
682 ms |
34568 KB |
Output is partially correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
12 ms |
23764 KB |
Output is partially correct |
| 2 |
Correct |
331 ms |
30324 KB |
Output is correct |
| 3 |
Partially correct |
705 ms |
32668 KB |
Output is partially correct |
| 4 |
Partially correct |
682 ms |
34568 KB |
Output is partially correct |
| 5 |
Partially correct |
123 ms |
36876 KB |
Output is partially correct |
| 6 |
Partially correct |
129 ms |
38280 KB |
Output is partially correct |
| 7 |
Partially correct |
139 ms |
37744 KB |
Output is partially correct |
| 8 |
Partially correct |
150 ms |
38852 KB |
Output is partially correct |
| 9 |
Partially correct |
631 ms |
33844 KB |
Output is partially correct |
| 10 |
Partially correct |
659 ms |
39344 KB |
Output is partially correct |
| 11 |
Partially correct |
471 ms |
39624 KB |
Output is partially correct |
| 12 |
Partially correct |
309 ms |
33736 KB |
Output is partially correct |
| 13 |
Partially correct |
91 ms |
32288 KB |
Output is partially correct |
| 14 |
Partially correct |
87 ms |
31972 KB |
Output is partially correct |
| 15 |
Partially correct |
87 ms |
31620 KB |
Output is partially correct |
| 16 |
Partially correct |
16 ms |
24060 KB |
Output is partially correct |
| 17 |
Partially correct |
187 ms |
30988 KB |
Output is partially correct |
| 18 |
Partially correct |
251 ms |
31008 KB |
Output is partially correct |
| 19 |
Partially correct |
243 ms |
32272 KB |
Output is partially correct |
| 20 |
Partially correct |
189 ms |
34996 KB |
Output is partially correct |
| 21 |
Partially correct |
412 ms |
37296 KB |
Output is partially correct |
| 22 |
Partially correct |
248 ms |
34108 KB |
Output is partially correct |
