#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for(int i = j; i < (int)k; i++)
#define pb push_back
typedef vector<int> vi;
const int N = 2e5 + 10;
vi C , X ,Y, nx[N];
int n, cnt = 1;
inline int inve(int sz , int l) {
int res = 0;
rep(i , 0 , sz)
if (l & (1 << i))
res ^= (1 << (sz - 1 - i));
return res;
}
int build2(vi &vec , int l = 0, int r = -1) {
if (r == -1) r = vec.size();
if (l == r - 1) return vec[inve(__builtin_ctz(vec.size()), l)];
int mid = l + r >> 1;
int me = cnt++;
X.pb(0), Y.pb(0);
int le = build2(vec , l , mid);
int re = build2(vec , mid , r);
X[me - 1] = le;
Y[me - 1] = re;
return -me;
}
void build(vi vec) {
//if (vec.empty()) return;
int sz = vec.size();
if(__builtin_popcount(sz) == 1) {
build2(vec);
return;
}
for (int i = 20; ~i; i--)
if (sz > (1 << i) - 1) {
vi local(vec.begin() , vec.begin() + (1 << i) - 1);
local.pb(-(cnt + (1 << i) - 1));
build2(local);
build(vi(vec.begin() + (1 << i) - 1 , vec.end()));
break;
}
}
void create_circuit(int M, vi A) {
n = A.size();
A.pb(0);
rep(i , 0 , n)
nx[A[i]].pb(A[i + 1]);
C.resize(M + 1);
C[0] = A[0];
rep(i , 1 , M + 1) {
if (nx[i].empty())
C[i] = 0;
else if (nx[i].size() == 1) {
C[i] = nx[i][0];
}
else {
C[i] = -cnt;
build(nx[i]);
}
}
answer(C , X , Y);
return;
}
Compilation message
doll.cpp: In function 'int build2(vi&, int, int)':
doll.cpp:28:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
28 | int mid = l + r >> 1;
| ~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
41 ms |
8656 KB |
Output is correct |
3 |
Correct |
37 ms |
8464 KB |
Output is correct |
4 |
Correct |
5 ms |
4940 KB |
Output is correct |
5 |
Correct |
19 ms |
6092 KB |
Output is correct |
6 |
Correct |
64 ms |
10144 KB |
Output is correct |
7 |
Correct |
4 ms |
4940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
41 ms |
8656 KB |
Output is correct |
3 |
Correct |
37 ms |
8464 KB |
Output is correct |
4 |
Correct |
5 ms |
4940 KB |
Output is correct |
5 |
Correct |
19 ms |
6092 KB |
Output is correct |
6 |
Correct |
64 ms |
10144 KB |
Output is correct |
7 |
Correct |
4 ms |
4940 KB |
Output is correct |
8 |
Correct |
58 ms |
11048 KB |
Output is correct |
9 |
Correct |
98 ms |
11520 KB |
Output is correct |
10 |
Correct |
131 ms |
14744 KB |
Output is correct |
11 |
Correct |
5 ms |
4940 KB |
Output is correct |
12 |
Correct |
6 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
41 ms |
8656 KB |
Output is correct |
3 |
Correct |
37 ms |
8464 KB |
Output is correct |
4 |
Correct |
5 ms |
4940 KB |
Output is correct |
5 |
Correct |
19 ms |
6092 KB |
Output is correct |
6 |
Correct |
64 ms |
10144 KB |
Output is correct |
7 |
Correct |
4 ms |
4940 KB |
Output is correct |
8 |
Correct |
58 ms |
11048 KB |
Output is correct |
9 |
Correct |
98 ms |
11520 KB |
Output is correct |
10 |
Correct |
131 ms |
14744 KB |
Output is correct |
11 |
Correct |
5 ms |
4940 KB |
Output is correct |
12 |
Correct |
6 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Incorrect |
117 ms |
13912 KB |
wrong motion |
15 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
4940 KB |
wrong motion |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
4940 KB |
wrong motion |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
4940 KB |
wrong motion |
2 |
Halted |
0 ms |
0 KB |
- |