#include <bits/stdc++.h>
#include "doll.h"
using namespace std;
#define SIZE(x) (int)x.size()
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define pb push_back
typedef vector<int> vi;
vi L, R, v, state;
int t=1, skip, s=0;
void build(int u, int l, int r) {
L.pb(0), R.pb(0), v.pb(0);
assert(u>=0 && u<SIZE(v));
if(l>r) {
v[u]=-1;
return;
}
if(skip>0 && r-l+1<=skip) {
v[u]=-1;
skip-=r-l+1;
return;
}
if(l==r) return;
v[u]=--s;
int m=(l+r)/2;
L[u] = t++;
build(L[u], l, m);
R[u] = t++;
build(R[u], m+1, r);
}
bool dfs(int u, int a) {
assert(u>=0 && u<SIZE(v));
if(u!=0 && v[u]==-1) return false;
if(!v[u]) {
v[u]=a;
return true;
}
state[u]^=1;
assert(v[L[u]]!=-1 || v[R[u]]!=-1);
if(state[u]) return dfs(L[u],a);
return dfs(R[u],a);
}
void create_circuit(int m, vi A) {
vi c(m+1);
c[0]=A[0];
forsn(i,1,m+1) c[i]=-1;
int n=SIZE(A), sz=1;
while(sz<n) sz*=2;
assert(sz>=n);
skip = sz-n;
build(0,1,sz);
assert(SIZE(L)==SIZE(R) && SIZE(v)==SIZE(L));
vi a;
forsn(i,1,n) a.pb(A[i]);
a.pb(0);
state.assign(SIZE(v),0);
forn(i,n) {
bool flag=0;
while(!flag) flag=dfs(0,a[i]);
}
vi x, y;
forn(i,SIZE(v)) {
if(L[i] && R[i]) {
x.pb(v[L[i]]);
y.pb(v[R[i]]);
}
}
answer(c,x,y);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
38 ms |
6352 KB |
Output is correct |
3 |
Correct |
35 ms |
6320 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
12 ms |
1372 KB |
Output is correct |
6 |
Correct |
53 ms |
9248 KB |
Output is correct |
7 |
Incorrect |
1 ms |
344 KB |
wrong serial number |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
38 ms |
6352 KB |
Output is correct |
3 |
Correct |
35 ms |
6320 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
12 ms |
1372 KB |
Output is correct |
6 |
Correct |
53 ms |
9248 KB |
Output is correct |
7 |
Incorrect |
1 ms |
344 KB |
wrong serial number |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
38 ms |
6352 KB |
Output is correct |
3 |
Correct |
35 ms |
6320 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
12 ms |
1372 KB |
Output is correct |
6 |
Correct |
53 ms |
9248 KB |
Output is correct |
7 |
Incorrect |
1 ms |
344 KB |
wrong serial number |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
612 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
69 ms |
10460 KB |
Output is correct |
3 |
Correct |
60 ms |
10764 KB |
Output is correct |
4 |
Correct |
100 ms |
15516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
69 ms |
10460 KB |
Output is correct |
3 |
Correct |
60 ms |
10764 KB |
Output is correct |
4 |
Correct |
100 ms |
15516 KB |
Output is correct |
5 |
Correct |
112 ms |
16636 KB |
Output is correct |
6 |
Correct |
115 ms |
16288 KB |
Output is correct |
7 |
Correct |
105 ms |
16404 KB |
Output is correct |
8 |
Correct |
106 ms |
16148 KB |
Output is correct |
9 |
Correct |
62 ms |
10688 KB |
Output is correct |
10 |
Correct |
114 ms |
16240 KB |
Output is correct |
11 |
Correct |
113 ms |
15880 KB |
Output is correct |
12 |
Correct |
60 ms |
10916 KB |
Output is correct |
13 |
Correct |
67 ms |
11052 KB |
Output is correct |
14 |
Correct |
67 ms |
11296 KB |
Output is correct |
15 |
Correct |
63 ms |
11552 KB |
Output is correct |
16 |
Correct |
2 ms |
600 KB |
Output is correct |
17 |
Correct |
64 ms |
10680 KB |
Output is correct |
18 |
Correct |
63 ms |
10680 KB |
Output is correct |
19 |
Correct |
66 ms |
10964 KB |
Output is correct |
20 |
Correct |
100 ms |
16148 KB |
Output is correct |
21 |
Correct |
98 ms |
15776 KB |
Output is correct |
22 |
Correct |
105 ms |
15952 KB |
Output is correct |