#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
int S;
vector<int> X, Y;
int make_switch(vector<int> left, vector<int> right)
{
if(left.size() != right.size()) return -(1 << 30);
if(left.size() == 1)
{
S++;
X.push_back(left[0]);
Y.push_back(right[0]);
return -S;
}
S++;
int id = S;
X.push_back(0);
Y.push_back(0);
int l;
vector<int> lft, rgt;
l = left.size();
lft.clear(); rgt.clear();
for(int i = 0; i < l / 2; i++)
lft.push_back(left[i]);
for(int i = l / 2; i < l; i++)
rgt.push_back(left[i]);
int sl = make_switch(lft, rgt);
l = right.size();
lft.clear(); rgt.clear();
for(int i = 0; i < l / 2; i++)
lft.push_back(right[i]);
for(int i = l / 2; i < l; i++)
rgt.push_back(right[i]);
int sr = make_switch(lft, rgt);
X[id - 1] = sl;
Y[id - 1] = sr;
return -id;
}
int make_switch(vector<int> v)
{
if(v.empty()) return 0;
if(v.size() == 1)
return v[0];
int l = v.size();
assert( (l & (l - 1)) == 0 );
vector<int> newv;
newv.resize(v.size());
int lg = 0;
for(lg = 0; (1 << lg) < v.size(); lg++);
for(int i = 0; i < v.size(); i++)
{
int msk = i;
int rmsk = 0;
for(int j = 0; j < lg; j++)
if((msk >> j) & 1)
rmsk |= (1 << (lg - j - 1));
newv[rmsk] = v[i];
}
vector<int> lft, rgt;
for(int i = 0; i < l / 2; i++)
lft.push_back(newv[i]);
for(int i = l / 2; i < l; i++)
rgt.push_back(newv[i]);
return make_switch(lft, rgt);
}
void create_circuit(int M, vector<int> A)
{
vector< vector<int> > v;
v.resize(M + 2);
int lst = 0;
for(int i = 0; i < A.size(); i++)
{
v[lst].push_back(A[i]);
lst = A[i];
}
v[lst].push_back(0);
vector<int> ex;
ex.resize(M + 1);
X.clear(), Y.clear();
S = 0;
for(int i = 0; i <= M; i++)
{
int l = v[i].size();
ex[i] = make_switch(v[i]);
}
answer(ex, X, Y);
}
Compilation message
doll.cpp: In function 'int make_switch(std::vector<int>)':
doll.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(lg = 0; (1 << lg) < v.size(); lg++);
| ~~~~~~~~~~^~~~~~~~~~
doll.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i = 0; i < A.size(); i++)
| ~~^~~~~~~~~~
doll.cpp:99:13: warning: unused variable 'l' [-Wunused-variable]
99 | int l = v[i].size();
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
45 ms |
6356 KB |
Output is correct |
3 |
Correct |
27 ms |
5196 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
13 ms |
3788 KB |
Output is correct |
6 |
Correct |
46 ms |
7628 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
45 ms |
6356 KB |
Output is correct |
3 |
Correct |
27 ms |
5196 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
13 ms |
3788 KB |
Output is correct |
6 |
Correct |
46 ms |
7628 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
65 ms |
7248 KB |
Output is correct |
9 |
Correct |
93 ms |
8560 KB |
Output is correct |
10 |
Correct |
111 ms |
11012 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
45 ms |
6356 KB |
Output is correct |
3 |
Correct |
27 ms |
5196 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
13 ms |
3788 KB |
Output is correct |
6 |
Correct |
46 ms |
7628 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
65 ms |
7248 KB |
Output is correct |
9 |
Correct |
93 ms |
8560 KB |
Output is correct |
10 |
Correct |
111 ms |
11012 KB |
Output is correct |
11 |
Correct |
1 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 |
Runtime error |
80 ms |
11428 KB |
Execution killed with signal 6 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
2 ms |
332 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
2 ms |
332 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |