ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#185144 | #3300. perm | Yansuan_HCl | 100 | 501ms | 16652kb | C++11 | 2.6kb | 2023-09-23 10:36:52 | 2023-09-23 12:01:03 |
answer
#include <bits/stdc++.h>
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline)) static
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
template <class T> using BS = basic_string<T>;
template <class T> void rd(T& s) {
int c = getchar(); T f = 1; s = 0;
while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); }
while (isdigit(c)) { s = s * 10 + (c ^ 48); c = getchar(); }
s *= f;
}
template <class T, class... Y> void rd(T& x, Y&... y) { rd(x), rd(y...); }
#define meow(...) fprintf(stderr, __VA_ARGS__)
#define Assert(e, v) if (!(e)) exit(v);
const int N = 300005;
int n, p[N], q[N], a[N];
bool vis[N], beg[N], le[N]; int shift[N];
vector<pair<int, int>> ri[N];
// 只需检查两个同余方程组是否相容
vector<pair<int, int>> equ; // x \equiv xi (mi)
// 加入一个新长度的环,一定存在 xi 使得有解
bool check(int x1, int m1, int x2, int m2) {
int g = __gcd(m1, m2);
return !(((x2 - x1) % g + g) % g);
}
bool tryMerge(int x1, int m1) {
for (auto pi : equ) {
int x2, m2; tie(x2, m2) = pi;
if (!check(x1, m1, x2, m2))
return 0;
}
return 1;
}
int main() {
rd(n);
U (i, 1, n) rd(p[i]);
U (i, 1, n) { rd(q[i]); a[q[i]] = i; }
U (i, 1, n) if (!vis[i]) {
beg[i] = 1;
int t = i, s = 0;
while (!vis[t]) {
vis[t] = 1;
ri[i].push_back({p[t], s});
t = q[t]; ++s;
}
}
// 最多有根号个不同的环长. 确定一个该长度的环,其余该长度的环已经确定
U (i, 1, n) sort(ri[i].begin(), ri[i].end());
U (i, 1, n) if (beg[i] && !le[ri[i].size()]) {
int m = ri[i].size();
le[m] = 1;
for (auto pi : ri[i]) {
int v, s; tie(v, s) = pi;
if (tryMerge(s, m)) {
equ.emplace_back(s, m);
shift[m] = s;
break;
}
}
}
int ans[N] {};
U (i, 1, n)
sort(ri[i].begin(), ri[i].end(), [](const pair<int, int> &x, const pair<int, int> &y) {
return x.second < y.second;
});
U (i, 1, n) if (beg[i]) {
int m = ri[i].size();
int t = i;
U (j, shift[m], m - 1) {
ans[t] = ri[i][j].first;
t = q[t];
}
U (j, 0, shift[m] - 1) {
ans[t] = ri[i][j].first;
t = q[t];
}
}
U (i, 1, n) printf("%d ", ans[i]);
puts("");
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 2ms
memory: 9420kb
input:
30 29 30 1 7 22 28 14 3 8 16 9 19 12 2 13 26 5 4 18 25 11 27 21 20 10 24 23 15 6 17 18 6 30 8 21 23 ...
output:
1 9 19 8 24 7 15 29 14 30 2 10 20 6 21 13 5 17 22 25 26 28 3 16 11 27 23 18 4 12
result:
ok single line: '1 9 19 8 24 7 15 29 14 30 2 10...25 26 28 3 16 11 27 23 18 4 12 '
Test #2:
score: 10
Accepted
time: 2ms
memory: 9416kb
input:
30 20 11 15 17 4 13 3 1 14 5 16 19 8 24 28 30 2 25 6 22 7 26 10 29 27 23 9 21 18 12 30 26 9 28 29 10...
output:
3 23 4 20 15 26 27 28 18 6 10 17 25 19 9 2 30 22 24 5 1 21 16 13 29 11 7 12 14 8
result:
ok single line: '3 23 4 20 15 26 27 28 18 6 10 ...4 5 1 21 16 13 29 11 7 12 14 8 '
Test #3:
score: 10
Accepted
time: 2ms
memory: 9416kb
input:
30 2 9 21 26 6 20 15 19 28 11 1 16 4 14 17 22 25 3 29 5 12 18 30 8 23 7 27 10 24 13 25 19 27 13 8 15...
output:
2 9 6 26 18 22 1 16 28 12 15 17 4 21 25 27 14 3 29 13 11 20 30 8 23 7 19 24 10 5
result:
ok single line: '2 9 6 26 18 22 1 16 28 12 15 1... 13 11 20 30 8 23 7 19 24 10 5 '
Test #4:
score: 10
Accepted
time: 4ms
memory: 9516kb
input:
3000 1637 2545 409 608 2128 1726 2455 649 2191 243 1150 2802 2594 172 1900 2291 180 551 2464 1242 13...
output:
1 2 1021 780 1484 55 2191 2198 2434 2163 2577 2694 1818 1150 560 1919 1457 2997 2006 22 1588 1064 24...
result:
ok single line: '1 2 1021 780 1484 55 2191 2198...3 1417 1724 2845 2721 525 1065 '
Test #5:
score: 10
Accepted
time: 0ms
memory: 9524kb
input:
3000 2376 2470 1094 58 1313 2753 1542 1824 2277 1231 1671 2215 2367 1484 1172 2827 575 170 1798 1193...
output:
1 961 2933 229 339 2706 2444 1860 2515 698 2786 603 1355 2183 2797 794 2145 181 920 1390 1260 1851 1...
result:
ok single line: '1 961 2933 229 339 2706 2444 1...754 37 265 2726 2092 2540 1605 '
Test #6:
score: 10
Accepted
time: 0ms
memory: 9512kb
input:
3000 1789 2658 744 416 2901 1286 1199 667 2615 924 320 965 424 1059 749 2789 115 501 716 1827 2999 8...
output:
1 11 2 896 2755 900 14 1600 2469 998 869 1452 1602 481 58 2623 494 2880 2654 2574 1714 280 643 918 2...
result:
ok single line: '1 11 2 896 2755 900 14 1600 24...2 750 2309 2337 2998 1363 1300 '
Test #7:
score: 10
Accepted
time: 125ms
memory: 16548kb
input:
300000 228152 15193 30036 66875 109817 29175 163606 3669 152371 236041 18586 155484 277731 58754 205...
output:
1 2 146287 287669 46549 206669 64713 118115 296299 239600 55567 109821 240985 5357 147595 150754 271...
result:
ok single line: '1 2 146287 287669 46549 206669...967 253810 166829 15588 140410 '
Test #8:
score: 10
Accepted
time: 118ms
memory: 16532kb
input:
300000 71560 266695 572 57132 289171 94391 77050 158872 200947 246751 256773 241649 169734 74034 244...
output:
1 244188 47 164966 6 3 43312 136764 36503 207243 179392 98757 50968 135118 11215 219356 291984 70986...
result:
ok single line: '1 244188 47 164966 6 3 43312 1...027 217275 42871 171535 246164 '
Test #9:
score: 10
Accepted
time: 126ms
memory: 16652kb
input:
300000 194566 98763 184442 247332 260756 58491 109889 291726 277133 181787 71535 119267 37847 117429...
output:
6 69 1 88165 40150 299582 145 7 187074 190674 139062 172546 237840 257444 227776 204279 267190 8 546...
result:
ok single line: '6 69 1 88165 40150 299582 145 ...853 113900 68638 152704 242253 '
Test #10:
score: 10
Accepted
time: 122ms
memory: 16236kb
input:
300000 176748 173676 111279 258027 193052 262726 237843 47577 290345 272809 106742 41377 85168 92156...
output:
21 1 253 192251 117408 274968 208678 52816 244419 126595 9732 255453 12196 50297 154650 87925 106283...
result:
ok single line: '21 1 253 192251 117408 274968 ...37 144291 147270 263644 125170 '