// moreflags=grader.cpp
// (I must have done this problem before...?)
#include "doll.h"
#ifndef LOCAL
#define NDEBUG 1
#endif
#include<cassert>
void create_circuit(int numTrigger, std::vector<int> steps) {
int numLayer=1; while((1<<numLayer)<(int)steps.size()+1) ++numLayer;
std::vector<int> base(numLayer+1);
base[0]=0;
for(int layer=0; layer<numLayer; ++layer)
base[layer+1]=base[layer]+(int(steps.size())>>(layer+1))+1;
auto const numSwitch=base.back();
auto const size=[&](int layer){
return base[layer+1]-base[layer];
};
assert(size(numLayer-1)==1);
auto const root=base.end()[-2];
std::vector<int> X(numSwitch), Y(numSwitch);
for(int layer=1; layer<numLayer;++layer)
for(int node=base[layer]; node<base[layer+1];++node){
auto const position1=(node-base[layer])*2;
Y[node]=-(1+( position1+base[layer-1] ));
X[node]=-(1+( position1+1<size(layer-1) ? position1+1+base[layer-1] : root ));
}
assert(base[0]==0);
int index=0; // into steps, with some special cases
if((steps.size()+1)%2!=0) --index;
for(int i=0; i<(1<<numLayer);++i){
int j=0;
for(int tmp=i, _=0; _<numLayer; ++_){ j=j<<1|(tmp&1); tmp>>=1; }
auto const node=(1<<(numLayer-1))-1-(j>>1); bool const y=j&1;
if(node<size(0)){
(y ? Y[node]: X[node])=(index==-1 ? -(root+1) : index<(int)steps.size() ? steps[index] : 0);
++index;
}
}
answer(std::vector<int>(numTrigger+1, -(root+1)), std::move(X), std::move(Y));
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
40 ms |
2964 KB |
Output is correct |
3 |
Correct |
51 ms |
2536 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
11 ms |
1052 KB |
Output is correct |
6 |
Correct |
48 ms |
3844 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 |
2964 KB |
Output is correct |
3 |
Correct |
51 ms |
2536 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
11 ms |
1052 KB |
Output is correct |
6 |
Correct |
48 ms |
3844 KB |
Output is correct |
7 |
Correct |
2 ms |
204 KB |
Output is correct |
8 |
Correct |
66 ms |
4228 KB |
Output is correct |
9 |
Correct |
60 ms |
4644 KB |
Output is correct |
10 |
Correct |
85 ms |
6496 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 |
2964 KB |
Output is correct |
3 |
Correct |
51 ms |
2536 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
11 ms |
1052 KB |
Output is correct |
6 |
Correct |
48 ms |
3844 KB |
Output is correct |
7 |
Correct |
2 ms |
204 KB |
Output is correct |
8 |
Correct |
66 ms |
4228 KB |
Output is correct |
9 |
Correct |
60 ms |
4644 KB |
Output is correct |
10 |
Correct |
85 ms |
6496 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 |
84 ms |
5992 KB |
Output is correct |
15 |
Correct |
59 ms |
3852 KB |
Output is correct |
16 |
Correct |
96 ms |
5812 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 |
95 ms |
6136 KB |
Output is correct |
21 |
Correct |
1 ms |
256 KB |
Output is correct |
22 |
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 |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
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 |
49 ms |
3344 KB |
Output is correct |
3 |
Correct |
55 ms |
3380 KB |
Output is correct |
4 |
Correct |
94 ms |
4948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
49 ms |
3344 KB |
Output is correct |
3 |
Correct |
55 ms |
3380 KB |
Output is correct |
4 |
Correct |
94 ms |
4948 KB |
Output is correct |
5 |
Correct |
116 ms |
5640 KB |
Output is correct |
6 |
Correct |
90 ms |
5572 KB |
Output is correct |
7 |
Correct |
98 ms |
5624 KB |
Output is correct |
8 |
Correct |
81 ms |
5268 KB |
Output is correct |
9 |
Correct |
89 ms |
3356 KB |
Output is correct |
10 |
Correct |
107 ms |
5236 KB |
Output is correct |
11 |
Correct |
73 ms |
4908 KB |
Output is correct |
12 |
Correct |
49 ms |
3364 KB |
Output is correct |
13 |
Correct |
68 ms |
3560 KB |
Output is correct |
14 |
Correct |
53 ms |
3732 KB |
Output is correct |
15 |
Correct |
52 ms |
3828 KB |
Output is correct |
16 |
Correct |
3 ms |
332 KB |
Output is correct |
17 |
Correct |
56 ms |
3372 KB |
Output is correct |
18 |
Correct |
60 ms |
3360 KB |
Output is correct |
19 |
Correct |
54 ms |
3368 KB |
Output is correct |
20 |
Correct |
81 ms |
5044 KB |
Output is correct |
21 |
Correct |
96 ms |
4904 KB |
Output is correct |
22 |
Correct |
103 ms |
4932 KB |
Output is correct |