#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;
int build2(vi &vec , int l = 0, int r = -1) {
if (r == -1) r = vec.size();
if (l == r - 1) return vec[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:20:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
20 | int mid = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
43 ms |
8716 KB |
Output is correct |
3 |
Correct |
38 ms |
8388 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
16 ms |
6092 KB |
Output is correct |
6 |
Correct |
52 ms |
10220 KB |
Output is correct |
7 |
Correct |
5 ms |
4888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
43 ms |
8716 KB |
Output is correct |
3 |
Correct |
38 ms |
8388 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
16 ms |
6092 KB |
Output is correct |
6 |
Correct |
52 ms |
10220 KB |
Output is correct |
7 |
Correct |
5 ms |
4888 KB |
Output is correct |
8 |
Correct |
65 ms |
11132 KB |
Output is correct |
9 |
Correct |
99 ms |
11464 KB |
Output is correct |
10 |
Correct |
137 ms |
14736 KB |
Output is correct |
11 |
Correct |
5 ms |
4940 KB |
Output is correct |
12 |
Correct |
4 ms |
4940 KB |
Output is correct |
13 |
Correct |
5 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
43 ms |
8716 KB |
Output is correct |
3 |
Correct |
38 ms |
8388 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
16 ms |
6092 KB |
Output is correct |
6 |
Correct |
52 ms |
10220 KB |
Output is correct |
7 |
Correct |
5 ms |
4888 KB |
Output is correct |
8 |
Correct |
65 ms |
11132 KB |
Output is correct |
9 |
Correct |
99 ms |
11464 KB |
Output is correct |
10 |
Correct |
137 ms |
14736 KB |
Output is correct |
11 |
Correct |
5 ms |
4940 KB |
Output is correct |
12 |
Correct |
4 ms |
4940 KB |
Output is correct |
13 |
Correct |
5 ms |
4940 KB |
Output is correct |
14 |
Incorrect |
146 ms |
13860 KB |
wrong motion |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
4940 KB |
wrong motion |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
4940 KB |
wrong motion |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
4940 KB |
wrong motion |
2 |
Halted |
0 ms |
0 KB |
- |