#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 200010;
vector <int> X, Y, C;
int n, m;
vector <int> urm[NMAX], act;
vector <int> build_ord(int h)
{
if (h == 0)
return { 0 };
auto x = build_ord(h - 1);
auto y = x;
for (auto & i : x)
i *= 2;
for (auto & i : y)
i = 2 * i + 1;
for (auto i : y)
x.push_back(i);
return x;
}
int build_switch(int h, int from, vector <int> & fii)
{
if (h != 0) {
int nod = X.size() + 1;
X.push_back(0);
Y.push_back(0);
int st = build_switch(h - 1, from, fii);
int dr = build_switch(h - 1, from + (1 << (h - 1)), fii);
X[nod - 1] = st;
Y[nod - 1] = dr;
return -nod;
}
return fii[from];
}
void create_circuit(int M, std::vector<int> A) {
n = A.size(), m = M;
urm[0].push_back(A[0]);
A.push_back(0);
for (int i = 0; i + 1 < A.size(); i++)
urm[A[i]].push_back(A[i + 1]);
C.resize(m + 1);
for (int i = 0; i <= m; i++) {
if (urm[i].empty())
continue;
int nr = urm[i].size();
int h = 0, root = -(X.size() + 1);
while ((1 << h) < nr)
h++;
auto ord = build_ord(h);
// o sa am ordinea ord cand apelez cv de adancime h
int decalaj = ord.size() - nr;
for (auto & j : ord) {
if (j < decalaj)
j = root;
else {
assert(j - decalaj < urm[i].size());
j = urm[i][j - decalaj];
}
}
C[i] = build_switch(h, 0, ord);
}
answer(C, X, Y);
}
Compilation message
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:46:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int i = 0; i + 1 < A.size(); i++)
| ~~~~~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from doll.cpp:2:
doll.cpp:66:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | assert(j - decalaj < urm[i].size());
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4940 KB |
Output is correct |
2 |
Correct |
40 ms |
8724 KB |
Output is correct |
3 |
Correct |
36 ms |
8380 KB |
Output is correct |
4 |
Correct |
5 ms |
4940 KB |
Output is correct |
5 |
Correct |
18 ms |
6164 KB |
Output is correct |
6 |
Correct |
57 ms |
10348 KB |
Output is correct |
7 |
Correct |
4 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4940 KB |
Output is correct |
2 |
Correct |
40 ms |
8724 KB |
Output is correct |
3 |
Correct |
36 ms |
8380 KB |
Output is correct |
4 |
Correct |
5 ms |
4940 KB |
Output is correct |
5 |
Correct |
18 ms |
6164 KB |
Output is correct |
6 |
Correct |
57 ms |
10348 KB |
Output is correct |
7 |
Correct |
4 ms |
4940 KB |
Output is correct |
8 |
Correct |
64 ms |
11136 KB |
Output is correct |
9 |
Correct |
103 ms |
11532 KB |
Output is correct |
10 |
Correct |
135 ms |
14736 KB |
Output is correct |
11 |
Correct |
4 ms |
4940 KB |
Output is correct |
12 |
Correct |
4 ms |
4940 KB |
Output is correct |
13 |
Correct |
4 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4940 KB |
Output is correct |
2 |
Correct |
40 ms |
8724 KB |
Output is correct |
3 |
Correct |
36 ms |
8380 KB |
Output is correct |
4 |
Correct |
5 ms |
4940 KB |
Output is correct |
5 |
Correct |
18 ms |
6164 KB |
Output is correct |
6 |
Correct |
57 ms |
10348 KB |
Output is correct |
7 |
Correct |
4 ms |
4940 KB |
Output is correct |
8 |
Correct |
64 ms |
11136 KB |
Output is correct |
9 |
Correct |
103 ms |
11532 KB |
Output is correct |
10 |
Correct |
135 ms |
14736 KB |
Output is correct |
11 |
Correct |
4 ms |
4940 KB |
Output is correct |
12 |
Correct |
4 ms |
4940 KB |
Output is correct |
13 |
Correct |
4 ms |
4940 KB |
Output is correct |
14 |
Correct |
136 ms |
16416 KB |
Output is correct |
15 |
Correct |
66 ms |
10884 KB |
Output is correct |
16 |
Correct |
100 ms |
13776 KB |
Output is correct |
17 |
Correct |
4 ms |
4940 KB |
Output is correct |
18 |
Correct |
4 ms |
4940 KB |
Output is correct |
19 |
Correct |
5 ms |
4940 KB |
Output is correct |
20 |
Correct |
109 ms |
15192 KB |
Output is correct |
21 |
Correct |
4 ms |
4940 KB |
Output is correct |
22 |
Correct |
4 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
4940 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
4 ms |
4920 KB |
Output is partially correct |
2 |
Correct |
50 ms |
10744 KB |
Output is correct |
3 |
Partially correct |
86 ms |
14748 KB |
Output is partially correct |
4 |
Partially correct |
92 ms |
15196 KB |
Output is partially correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
4 ms |
4920 KB |
Output is partially correct |
2 |
Correct |
50 ms |
10744 KB |
Output is correct |
3 |
Partially correct |
86 ms |
14748 KB |
Output is partially correct |
4 |
Partially correct |
92 ms |
15196 KB |
Output is partially correct |
5 |
Partially correct |
152 ms |
18120 KB |
Output is partially correct |
6 |
Partially correct |
163 ms |
19460 KB |
Output is partially correct |
7 |
Partially correct |
135 ms |
19008 KB |
Output is partially correct |
8 |
Partially correct |
142 ms |
20100 KB |
Output is partially correct |
9 |
Partially correct |
81 ms |
14516 KB |
Output is partially correct |
10 |
Partially correct |
162 ms |
19544 KB |
Output is partially correct |
11 |
Partially correct |
174 ms |
20820 KB |
Output is partially correct |
12 |
Partially correct |
82 ms |
14952 KB |
Output is partially correct |
13 |
Partially correct |
109 ms |
13556 KB |
Output is partially correct |
14 |
Partially correct |
87 ms |
13196 KB |
Output is partially correct |
15 |
Partially correct |
86 ms |
12836 KB |
Output is partially correct |
16 |
Partially correct |
6 ms |
5196 KB |
Output is partially correct |
17 |
Partially correct |
73 ms |
12184 KB |
Output is partially correct |
18 |
Partially correct |
96 ms |
13076 KB |
Output is partially correct |
19 |
Partially correct |
74 ms |
12760 KB |
Output is partially correct |
20 |
Partially correct |
107 ms |
16196 KB |
Output is partially correct |
21 |
Partially correct |
124 ms |
18732 KB |
Output is partially correct |
22 |
Partially correct |
95 ms |
15396 KB |
Output is partially correct |