UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#185144#3300. permYansuan_HCl100501ms16652kbC++112.6kb2023-09-23 10:36:522023-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 '