#include "doll.h"
#include<vector>
#include<algorithm>
#include<utility>
#include<array>
#include<map>
#include<set>
#include<cassert>
#include<iostream>
using namespace std;
#define V vector
#define rep(i,a,b) for(int i=a; i<(int)b; i++)
#define nl '\n'
#define _ << " " <<
#define dbg(x) cout << "?" << #x << " : " << x << endl;
const int N = 4e5+5;
const int B = 3;
int n, m;
V<int> a;
V<int> c, lc, rc;
int make(){
lc.push_back(-1);
rc.push_back(-1);
return -(int)lc.size();
}
int f(int x){
return -x-1;
}
V<int> leaves;
bool stat[N];
void create_circuit(int _m,V<int> _a){
a.swap(_a); a.push_back(0);
n = a.size(); m = _m;
// build tree
V<int> v(n,0);
while(v.size() > 1){
V<int> nxt;
if(v.size()%2==1){
int x=1, y=v[0];
int z = make();
lc[f(z)] = x; rc[f(z)] = y;
nxt.push_back(z);
}
for(int i=v.size()%2; i<(int)v.size(); i+=2){
int x=v[i], y=v[i+1];
int z = make();
lc[f(z)] = x; rc[f(z)] = y;
nxt.push_back(z);
}
v.swap(nxt);
}
for(int x=-1; ; x--){
int idx = -x-1;
if(lc[idx]==1) lc[idx] = -lc.size();
if(rc[idx]==1) rc[idx] = -rc.size();
// cout << x _ lc[idx] _ rc[idx] << nl;
if(x==-(int)lc.size()) break;
}
c = V<int>(m+1, -lc.size());
// return;
// simulate to find order of leaves
// dbg("LEAVES");
int x = -lc.size();
while((int)leaves.size() < n){
// dbg(x);
int idx = -x-1, y;
if(stat[idx]==0) y = lc[idx];
else y = rc[idx];
stat[idx] ^= 1;
if(y==0){
// cout << "LEAF" << nl;
// dbg(x);
leaves.push_back(x);
x = -lc.size();
}
else{
x = y;
}
}
rep(i,0,N) stat[i] = 0;
rep(i,0,n){
x = leaves[i];
int idx = -x-1;
if(lc[idx]==0){
lc[idx] = a[i];
}
else{
rc[idx] = a[i];
}
}
answer(c,lc,rc);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
43 ms |
6212 KB |
Output is correct |
3 |
Correct |
38 ms |
5788 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
10 ms |
1844 KB |
Output is correct |
6 |
Correct |
58 ms |
8100 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
43 ms |
6212 KB |
Output is correct |
3 |
Correct |
38 ms |
5788 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
10 ms |
1844 KB |
Output is correct |
6 |
Correct |
58 ms |
8100 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
76 ms |
9944 KB |
Output is correct |
9 |
Correct |
85 ms |
10512 KB |
Output is correct |
10 |
Correct |
115 ms |
14376 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
43 ms |
6212 KB |
Output is correct |
3 |
Correct |
38 ms |
5788 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
10 ms |
1844 KB |
Output is correct |
6 |
Correct |
58 ms |
8100 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
76 ms |
9944 KB |
Output is correct |
9 |
Correct |
85 ms |
10512 KB |
Output is correct |
10 |
Correct |
115 ms |
14376 KB |
Output is correct |
11 |
Correct |
1 ms |
596 KB |
Output is correct |
12 |
Correct |
1 ms |
596 KB |
Output is correct |
13 |
Correct |
1 ms |
596 KB |
Output is correct |
14 |
Correct |
113 ms |
13360 KB |
Output is correct |
15 |
Correct |
70 ms |
9124 KB |
Output is correct |
16 |
Correct |
108 ms |
12944 KB |
Output is correct |
17 |
Correct |
1 ms |
596 KB |
Output is correct |
18 |
Correct |
1 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
596 KB |
Output is correct |
20 |
Correct |
110 ms |
13572 KB |
Output is correct |
21 |
Correct |
1 ms |
608 KB |
Output is correct |
22 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
688 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
1 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
67 ms |
8456 KB |
Output is correct |
3 |
Correct |
64 ms |
8388 KB |
Output is correct |
4 |
Correct |
102 ms |
11836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Correct |
67 ms |
8456 KB |
Output is correct |
3 |
Correct |
64 ms |
8388 KB |
Output is correct |
4 |
Correct |
102 ms |
11836 KB |
Output is correct |
5 |
Correct |
105 ms |
12960 KB |
Output is correct |
6 |
Correct |
103 ms |
12776 KB |
Output is correct |
7 |
Correct |
104 ms |
12816 KB |
Output is correct |
8 |
Correct |
101 ms |
12552 KB |
Output is correct |
9 |
Correct |
67 ms |
8552 KB |
Output is correct |
10 |
Correct |
100 ms |
12452 KB |
Output is correct |
11 |
Correct |
97 ms |
12200 KB |
Output is correct |
12 |
Correct |
70 ms |
8692 KB |
Output is correct |
13 |
Correct |
68 ms |
8952 KB |
Output is correct |
14 |
Correct |
71 ms |
9068 KB |
Output is correct |
15 |
Correct |
68 ms |
9120 KB |
Output is correct |
16 |
Correct |
2 ms |
960 KB |
Output is correct |
17 |
Correct |
61 ms |
8172 KB |
Output is correct |
18 |
Correct |
64 ms |
8684 KB |
Output is correct |
19 |
Correct |
65 ms |
8704 KB |
Output is correct |
20 |
Correct |
100 ms |
12468 KB |
Output is correct |
21 |
Correct |
97 ms |
12216 KB |
Output is correct |
22 |
Correct |
98 ms |
12168 KB |
Output is correct |