#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
vector<vector<int>> switches;
vector<pair<int, int> > leaves;
int swcnt = 0;
void rec(int root, int h){
// binary tree
for (int i = 0; i < 2; ++i) {
if (h == 1) {
leaves.push_back({root, i});
} else {
swcnt++;
switches[i][root - 1] = -swcnt;
rec(swcnt, h - 1);
}
}
}
void create_circuit(int M, vector<int> A) {
int N = A.size();
vector<vector<int>> G(M+1, vector<int>());
for(int i=0; i<N; ++i){
if(i == N - 1){
G[A[i]].push_back(0);
} else {
G[A[i]].push_back(A[i+1]);
}
}
// compute the log2
vector<int> l2(N+1, 0);
l2[1] = 0;
for(int i=2; i<N+1; ++i)
l2[i] = l2[(i+1)/2] + 1;
int totalSwitches = 0;
for(int i=1; i<=M; ++i){
if(G[i].size() > 1){
totalSwitches += 2*(1<<(l2[G[i].size()] - 1)) - 1;
}
}
vector<int> C = vector<int>(M+1, 0);
switches = vector<vector<int>>(2, vector<int>(totalSwitches, 0));
C[0] = A[0];
for(int i=1; i<=M; ++i){
// dumb connection
if(G[i].size() == 0){
C[i] = i;
continue;
}
//connect with the next one
if(G[i].size() == 1){
C[i] = G[i][0];
continue;
}
swcnt++;
C[i] = -swcnt;
int switchRoot = C[i];
// build the switch tree and get the leaves
leaves.clear();
int height = l2[G[i].size()];
rec(-C[i], height);
// save the last element to swap later
int lstp = 0;
for(int it = 0; it < (1<<height); ++it) {
int rev = 0;
int aux = it;
int bt = height - 1;
// reverse bits
while(aux){
if(aux&1)
rev |= (1<<bt);
aux/=2;
bt--;
}
int lf = leaves[rev].first;
int ls = leaves[rev].second;
if (it < G[i].size()) {
switches[ls][lf - 1] = G[i][it];
lstp = rev;
} else {
switches[ls][lf - 1] = switchRoot;
}
}
if(G[i].size() < (1<<height)) {
swap(switches[leaves[lstp].second][leaves[lstp].first - 1],
switches[1][leaves[leaves.size() - 1].first - 1]);
}
}
/*
for(auto el: C){
cout<<el<<" ";
}
cout<<"\n";
for(auto el: X){
cout<<el<<" ";
}
cout<<"\n";
for(auto el: Y){
cout<<el<<" ";
}
cout<<"\n";
*/
answer(C, switches[0], switches[1]);
}
Compilation message
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | if (it < G[i].size()) {
| ~~~^~~~~~~~~~~~~
doll.cpp:106:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
106 | if(G[i].size() < (1<<height)) {
| ~~~~~~~~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
38 ms |
6536 KB |
Output is correct |
3 |
Correct |
29 ms |
5448 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
14 ms |
3788 KB |
Output is correct |
6 |
Correct |
44 ms |
8072 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
38 ms |
6536 KB |
Output is correct |
3 |
Correct |
29 ms |
5448 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
14 ms |
3788 KB |
Output is correct |
6 |
Correct |
44 ms |
8072 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
67 ms |
7716 KB |
Output is correct |
9 |
Correct |
65 ms |
9116 KB |
Output is correct |
10 |
Correct |
90 ms |
11568 KB |
Output is correct |
11 |
Correct |
2 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
38 ms |
6536 KB |
Output is correct |
3 |
Correct |
29 ms |
5448 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
14 ms |
3788 KB |
Output is correct |
6 |
Correct |
44 ms |
8072 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
67 ms |
7716 KB |
Output is correct |
9 |
Correct |
65 ms |
9116 KB |
Output is correct |
10 |
Correct |
90 ms |
11568 KB |
Output is correct |
11 |
Correct |
2 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
182 ms |
11688 KB |
Output is correct |
15 |
Correct |
83 ms |
6304 KB |
Output is correct |
16 |
Correct |
97 ms |
9436 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
113 ms |
11380 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
1 ms |
204 KB |
Output is partially correct |
2 |
Correct |
56 ms |
6488 KB |
Output is correct |
3 |
Partially correct |
104 ms |
12100 KB |
Output is partially correct |
4 |
Partially correct |
119 ms |
11792 KB |
Output is partially correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
1 ms |
204 KB |
Output is partially correct |
2 |
Correct |
56 ms |
6488 KB |
Output is correct |
3 |
Partially correct |
104 ms |
12100 KB |
Output is partially correct |
4 |
Partially correct |
119 ms |
11792 KB |
Output is partially correct |
5 |
Partially correct |
136 ms |
14292 KB |
Output is partially correct |
6 |
Partially correct |
126 ms |
16000 KB |
Output is partially correct |
7 |
Partially correct |
154 ms |
15516 KB |
Output is partially correct |
8 |
Partially correct |
126 ms |
16888 KB |
Output is partially correct |
9 |
Partially correct |
94 ms |
11976 KB |
Output is partially correct |
10 |
Partially correct |
141 ms |
18056 KB |
Output is partially correct |
11 |
Partially correct |
128 ms |
17552 KB |
Output is partially correct |
12 |
Partially correct |
89 ms |
11544 KB |
Output is partially correct |
13 |
Partially correct |
92 ms |
10480 KB |
Output is partially correct |
14 |
Partially correct |
81 ms |
10072 KB |
Output is partially correct |
15 |
Partially correct |
104 ms |
9564 KB |
Output is partially correct |
16 |
Partially correct |
5 ms |
460 KB |
Output is partially correct |
17 |
Partially correct |
87 ms |
8952 KB |
Output is partially correct |
18 |
Partially correct |
98 ms |
8972 KB |
Output is partially correct |
19 |
Partially correct |
76 ms |
9612 KB |
Output is partially correct |
20 |
Partially correct |
104 ms |
12260 KB |
Output is partially correct |
21 |
Partially correct |
114 ms |
15068 KB |
Output is partially correct |
22 |
Partially correct |
94 ms |
11312 KB |
Output is partially correct |