#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
int S;
vector<int> X, Y;
vector<int> newv;
int make_switch(int st, int dr, int idd = -1)
{
if(st == dr) return newv[st];
if(st + 1 == dr)
{
if(idd == -1)
{
S++;
X.push_back(newv[st]);
Y.push_back(newv[dr]);
return -S;
}
else
{
X[idd - 1] = newv[st];
Y[idd - 1] = newv[dr];
return -idd;
}
}
int id = -1;
if(idd == -1)
{
S++;
id = S;
X.push_back(0);
Y.push_back(0);
}
else
id = idd;
int mij = st + (dr - st) / 2;
int sl = make_switch(st, mij);
int sr = make_switch(mij + 1, dr);
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];
S++;
X.push_back(0);
Y.push_back(0);
int l = v.size();
int lst = v.back();
v.pop_back();
while( (l & (l - 1)) != 0 )
{
v.push_back(-S);
l++;
}
v.push_back(lst);
newv.clear();
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];
}
return make_switch(0, l - 1, S);
}
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:74:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(lg = 0; (1 << lg) < v.size(); lg++);
| ~~~~~~~~~~^~~~~~~~~~
doll.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 0; i < v.size(); i++)
| ~~^~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i = 0; i < A.size(); i++)
| ~~^~~~~~~~~~
doll.cpp:107:13: warning: unused variable 'l' [-Wunused-variable]
107 | int l = v[i].size();
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
40 ms |
6296 KB |
Output is correct |
3 |
Correct |
45 ms |
5172 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
15 ms |
3812 KB |
Output is correct |
6 |
Correct |
54 ms |
7700 KB |
Output is correct |
7 |
Correct |
2 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
40 ms |
6296 KB |
Output is correct |
3 |
Correct |
45 ms |
5172 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
15 ms |
3812 KB |
Output is correct |
6 |
Correct |
54 ms |
7700 KB |
Output is correct |
7 |
Correct |
2 ms |
204 KB |
Output is correct |
8 |
Correct |
71 ms |
7160 KB |
Output is correct |
9 |
Correct |
71 ms |
8580 KB |
Output is correct |
10 |
Correct |
143 ms |
11064 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
40 ms |
6296 KB |
Output is correct |
3 |
Correct |
45 ms |
5172 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
15 ms |
3812 KB |
Output is correct |
6 |
Correct |
54 ms |
7700 KB |
Output is correct |
7 |
Correct |
2 ms |
204 KB |
Output is correct |
8 |
Correct |
71 ms |
7160 KB |
Output is correct |
9 |
Correct |
71 ms |
8580 KB |
Output is correct |
10 |
Correct |
143 ms |
11064 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 |
Correct |
110 ms |
10948 KB |
Output is correct |
15 |
Correct |
58 ms |
5832 KB |
Output is correct |
16 |
Correct |
138 ms |
8600 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 |
106 ms |
10608 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 |
58 ms |
5480 KB |
Output is correct |
3 |
Partially correct |
94 ms |
11044 KB |
Output is partially correct |
4 |
Partially correct |
112 ms |
10732 KB |
Output is partially correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
1 ms |
204 KB |
Output is partially correct |
2 |
Correct |
58 ms |
5480 KB |
Output is correct |
3 |
Partially correct |
94 ms |
11044 KB |
Output is partially correct |
4 |
Partially correct |
112 ms |
10732 KB |
Output is partially correct |
5 |
Partially correct |
119 ms |
12196 KB |
Output is partially correct |
6 |
Partially correct |
134 ms |
13492 KB |
Output is partially correct |
7 |
Partially correct |
130 ms |
13000 KB |
Output is partially correct |
8 |
Partially correct |
129 ms |
14124 KB |
Output is partially correct |
9 |
Partially correct |
91 ms |
8668 KB |
Output is partially correct |
10 |
Partially correct |
139 ms |
14416 KB |
Output is partially correct |
11 |
Partially correct |
135 ms |
14668 KB |
Output is partially correct |
12 |
Partially correct |
87 ms |
9708 KB |
Output is partially correct |
13 |
Partially correct |
85 ms |
8872 KB |
Output is partially correct |
14 |
Partially correct |
86 ms |
8620 KB |
Output is partially correct |
15 |
Partially correct |
78 ms |
8152 KB |
Output is partially correct |
16 |
Partially correct |
3 ms |
460 KB |
Output is partially correct |
17 |
Partially correct |
68 ms |
7572 KB |
Output is partially correct |
18 |
Partially correct |
71 ms |
7508 KB |
Output is partially correct |
19 |
Partially correct |
102 ms |
8116 KB |
Output is partially correct |
20 |
Partially correct |
101 ms |
10312 KB |
Output is partially correct |
21 |
Partially correct |
129 ms |
12488 KB |
Output is partially correct |
22 |
Partially correct |
134 ms |
9572 KB |
Output is partially correct |