#ifdef LOCAL
#else
#include "doll.h"
#endif
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int inf = 2e09; ll infll = 2e18;
vector<int> X, Y;
int cur = 1;
void dfs(int x, int pref, int s, int e, vector<int> &t){
int mid = (s+e)>>1;
X.emplace_back(0), Y.emplace_back(0);
if(mid < pref) X[x-1] = -1;
else{
if(s != mid) X[x-1] = -(++cur), dfs(cur, pref, s, mid, t);
else X[x-1] = t[s];
}
if(mid+1 != e) Y[x-1] = -(++cur), dfs(cur, pref, mid+1, e, t);
else Y[x-1] = t[e];
}
void create_circuit(int m, vector<int> A){
A.emplace_back(0); int n = ssize(A);
vector<int> c(m+1, -1);
int base = 1, log = 0;
while(base < n) base <<= 1, ++log;
vector<int> t(base);
for(int i = 0; i < base; ++i) t[i] = i;
vector<int> tmp0, tmp1, where(base);
for(int len = base; len > 2; len >>= 1){
for(int p = 0; p < base; p += len){
tmp0 = vector<int>(), tmp1 = vector<int>();
for(int i = p; i < p+len; ++i) if(i&1) tmp1.emplace_back(t[i]);
else tmp0.emplace_back(t[i]);
for(int i = 0; i < len/2; ++i) t[i+p] = tmp0[i];
for(int i = len/2; i < len; ++i) t[i+p] = tmp1[i-len/2];
}
}
for(int i = 0; i < base; ++i) where[t[i]] = i;
vector<int> tmp;
int pref = base-ssize(A);
for(int i = base-ssize(A); i < base; ++i) tmp.emplace_back(t[i]);
sort(tmp.begin(), tmp.end());
for(int i = 0; i < base-ssize(A); ++i) t[i] = -1;
for(int i = 0; i < ssize(A); ++i) t[where[tmp[i]]] = A[i];
dfs(1, pref, 0, base-1, t);
#ifdef LOCAL
for(int i = 0; i < ssize(X); ++i) printf("%d %d\n", X[i], Y[i]);
#else
answer(c, X, Y);
#endif
}
#ifdef LOCAL
int main(){
int T = 1;
for(++T; --T; ){
int m, n; scanf("%d%d", &m, &n);
vector<int> A(n);
for(int i = 0; i < n; ++i) scanf("%d", &A[i]);
create_circuit(m, A);
}
return 0;
}
#endif
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
36 ms |
5676 KB |
Output is correct |
3 |
Correct |
34 ms |
5152 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
7 ms |
1372 KB |
Output is correct |
6 |
Correct |
48 ms |
6904 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
36 ms |
5676 KB |
Output is correct |
3 |
Correct |
34 ms |
5152 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
7 ms |
1372 KB |
Output is correct |
6 |
Correct |
48 ms |
6904 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
66 ms |
8744 KB |
Output is correct |
9 |
Correct |
67 ms |
9000 KB |
Output is correct |
10 |
Correct |
91 ms |
12612 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
36 ms |
5676 KB |
Output is correct |
3 |
Correct |
34 ms |
5152 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
7 ms |
1372 KB |
Output is correct |
6 |
Correct |
48 ms |
6904 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
66 ms |
8744 KB |
Output is correct |
9 |
Correct |
67 ms |
9000 KB |
Output is correct |
10 |
Correct |
91 ms |
12612 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
93 ms |
11588 KB |
Output is correct |
15 |
Correct |
73 ms |
8608 KB |
Output is correct |
16 |
Correct |
86 ms |
11452 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
94 ms |
11884 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
436 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
412 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
61 ms |
7976 KB |
Output is correct |
3 |
Correct |
60 ms |
7976 KB |
Output is correct |
4 |
Correct |
81 ms |
10816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
61 ms |
7976 KB |
Output is correct |
3 |
Correct |
60 ms |
7976 KB |
Output is correct |
4 |
Correct |
81 ms |
10816 KB |
Output is correct |
5 |
Correct |
89 ms |
11328 KB |
Output is correct |
6 |
Correct |
85 ms |
11092 KB |
Output is correct |
7 |
Correct |
85 ms |
11328 KB |
Output is correct |
8 |
Correct |
82 ms |
11056 KB |
Output is correct |
9 |
Correct |
60 ms |
7972 KB |
Output is correct |
10 |
Correct |
81 ms |
11072 KB |
Output is correct |
11 |
Correct |
81 ms |
10992 KB |
Output is correct |
12 |
Correct |
60 ms |
7972 KB |
Output is correct |
13 |
Correct |
62 ms |
8088 KB |
Output is correct |
14 |
Correct |
67 ms |
8032 KB |
Output is correct |
15 |
Correct |
62 ms |
8236 KB |
Output is correct |
16 |
Correct |
2 ms |
604 KB |
Output is correct |
17 |
Correct |
47 ms |
8524 KB |
Output is correct |
18 |
Correct |
59 ms |
7976 KB |
Output is correct |
19 |
Correct |
68 ms |
8116 KB |
Output is correct |
20 |
Correct |
82 ms |
10820 KB |
Output is correct |
21 |
Correct |
82 ms |
10816 KB |
Output is correct |
22 |
Correct |
82 ms |
10788 KB |
Output is correct |