#include "doll.h"
#include<cstdio>
#include<algorithm>
#include<queue>
#define N_ 201000
using namespace std;
int n, m, Out[N_], cnt, chk[N_*10], PV;
int RR[N_ * 10][2], vv[N_*10], Num[N_*10], ReNum[N_*10];
vector<int>E[N_], TP;
void Go(int a, int L, int cur, int ed) {
if (L == 1) {
if (RR[a][cur & 1]) {
RR[RR[a][cur & 1]][0] = ed;
return;
}
RR[a][cur & 1] = ed;
return;
}
if (!RR[a][cur & 1])RR[a][cur & 1] = ++cnt;
Go(RR[a][cur & 1], L - 1, cur >> 1, ed);
}
int Make() {
int ret = cnt + 1;
int i, sz = 1, cc = 0, j;
int L = TP.size();
while (sz < L) sz *= 2, cc++;
for (i = 1; i < sz/2; i++) {
RR[cnt + i][0] = cnt + i * 2;
RR[cnt + i][1] = cnt + i * 2 + 1;
}
int ccc = 0;
for (i = 0; i < sz; i++) {
int t = 0;
for (j = 0; j < cc; j++) {
t = t * 2 + ((i >> j) & 1);
}
int nxt;
if (t < sz - L) {
nxt = ret;
}
if (t >= sz - L) {
nxt = -TP[ccc++];
}
RR[cnt + sz / 2 + (t >> 1)][t & 1] = nxt;
}
for (i = cnt + sz - 1; i >= ret; i--) {
int x = i - cnt;
if (RR[i][0] >= 0 && RR[i][1] >= 0 && RR[i][0] == ret && RR[i][1] == ret) {
RR[cnt + x / 2][x & 1] = ret;
vv[i] = 1;
}
}
cnt += sz - 1;
return -ret;
}
void create_circuit(int M, std::vector<int> A) {
n = A.size();
m = M;
E[0].push_back(A[0]);
int i;
for (i = 0; i < n - 1; i++) {
E[A[i]].push_back(A[i + 1]);
}
E[A[n - 1]].push_back(0);
for (i = 0; i <= M; i++) {
if (E[i].size() == 0) Out[i] = 0;
else if (E[i].size() == 1)Out[i] = E[i][0];
else {
TP = E[i];
Out[i] = Make();
}
}
int ct = 0;
for (i = 1; i <= cnt; i++) {
if (!vv[i]) {
Num[i] = ++ct;
ReNum[ct] = i;
}
}
vector<int>C(m+1), X(ct), Y(ct);
for (i = 0; i <= m; i++)C[i] = Out[i];
for (i = 0; i < ct; i++) {
int x = RR[ReNum[i + 1]][0];
int y = RR[ReNum[i + 1]][1];
if (x > 0)x = Num[x];
if (y > 0)y = Num[y];
x = -x, y = -y;
X[i] = x, Y[i] = y;
}
answer(C, X, Y);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
48 ms |
9132 KB |
Output is correct |
3 |
Correct |
34 ms |
8584 KB |
Output is correct |
4 |
Correct |
5 ms |
4904 KB |
Output is correct |
5 |
Correct |
20 ms |
6584 KB |
Output is correct |
6 |
Correct |
65 ms |
10468 KB |
Output is correct |
7 |
Correct |
4 ms |
4988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
4940 KB |
Output is correct |
2 |
Correct |
48 ms |
9132 KB |
Output is correct |
3 |
Correct |
34 ms |
8584 KB |
Output is correct |
4 |
Correct |
5 ms |
4904 KB |
Output is correct |
5 |
Correct |
20 ms |
6584 KB |
Output is correct |
6 |
Correct |
65 ms |
10468 KB |
Output is correct |
7 |
Correct |
4 ms |
4988 KB |
Output is correct |
8 |
Correct |
67 ms |
11724 KB |
Output is correct |
9 |
Correct |
67 ms |
12052 KB |
Output is correct |
10 |
Correct |
127 ms |
15128 KB |
Output is correct |
11 |
Correct |
6 ms |
5036 KB |
Output is correct |
12 |
Correct |
5 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 |
48 ms |
9132 KB |
Output is correct |
3 |
Correct |
34 ms |
8584 KB |
Output is correct |
4 |
Correct |
5 ms |
4904 KB |
Output is correct |
5 |
Correct |
20 ms |
6584 KB |
Output is correct |
6 |
Correct |
65 ms |
10468 KB |
Output is correct |
7 |
Correct |
4 ms |
4988 KB |
Output is correct |
8 |
Correct |
67 ms |
11724 KB |
Output is correct |
9 |
Correct |
67 ms |
12052 KB |
Output is correct |
10 |
Correct |
127 ms |
15128 KB |
Output is correct |
11 |
Correct |
6 ms |
5036 KB |
Output is correct |
12 |
Correct |
5 ms |
4940 KB |
Output is correct |
13 |
Correct |
5 ms |
4940 KB |
Output is correct |
14 |
Correct |
134 ms |
17572 KB |
Output is correct |
15 |
Correct |
61 ms |
11472 KB |
Output is correct |
16 |
Correct |
137 ms |
14732 KB |
Output is correct |
17 |
Correct |
4 ms |
4940 KB |
Output is correct |
18 |
Correct |
6 ms |
4940 KB |
Output is correct |
19 |
Correct |
6 ms |
4940 KB |
Output is correct |
20 |
Correct |
124 ms |
16164 KB |
Output is correct |
21 |
Correct |
5 ms |
4960 KB |
Output is correct |
22 |
Correct |
5 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
4940 KB |
wrong motion |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4936 KB |
Output is correct |
2 |
Correct |
53 ms |
12308 KB |
Output is correct |
3 |
Correct |
67 ms |
14424 KB |
Output is correct |
4 |
Correct |
88 ms |
16864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4936 KB |
Output is correct |
2 |
Correct |
53 ms |
12308 KB |
Output is correct |
3 |
Correct |
67 ms |
14424 KB |
Output is correct |
4 |
Correct |
88 ms |
16864 KB |
Output is correct |
5 |
Incorrect |
154 ms |
20384 KB |
wrong serial number |
6 |
Halted |
0 ms |
0 KB |
- |