求调(对拍找不到错的)
查看原帖
求调(对拍找不到错的)
761114
yyym楼主2024/9/18 23:41
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int N = 200010;

int n;
int P[N], A[N], ans[N];
int a[N], b[N], tem[N], count_[N];
int m;
bitset<N> vis;

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1 ; i <= n ; i ++) cin >> P[i];
    for(int i = 1 ; i <= n ; i ++) cin >> A[i];
    for(int i = 1 ; i <= n ; i ++) {
        if(vis[i] == 1) continue;
        vector<int> p, q; int t = P[i]; vis[i] = 1;
        p.push_back(i); q.push_back(A[i]);
        while(t != i) {
            p.push_back(t); q.push_back(A[t]);
            vis[t] = 1; t = P[t];
        }
        int len = p.size();
        for(int j = 0 ; j <= len ; j ++) count_[j] = 0;
        for(int j = 1 ; j <= m ; j ++) {
            for(int k = 0 ; k < len ; k ++) tem[k] = 0;
            for(int k = 0 ; k < len ; k ++)
                tem[(((k * a[j]) % len) + b[j]) % len] = 1;
            for(int k = 0 ; k < len ; k ++) {
                if(tem[k]) count_[k] ++;
            }
        }
        int Min = INT_MAX; int apos = -1;
        for(int j = 0 ; j < len ; j ++) {
            if(count_[j] != m) continue;
            if(q[j] < Min) {Min = q[j]; apos = j; };
        }
        m ++; a[m] = len; b[m] = apos;
        for(int j = 0 ; j < len ; j ++, apos ++, apos %= len) {
            ans[p[j]] = q[apos];
        }
    }
    for(int i = 1 ; i <= n ; i ++)
        cout << ans[i] << " \n"[i == n];
    return 0;
}
2024/9/18 23:41
加载中...