置换

Time Limit: 10 Sec Memory Limit: 256 MB

Description

定义一个置换Р的平方Q为对[1,2,3,… ,n-1,n]做两次该置换得到的排列，即 $Q_i = P_{P_i} $

现在已知一个置换的平方，求该置换。

Input

第一行一个整数n表示排列长度。

第二行n个整数表示所求置换的平方。

Output

若有解则输出一行n个数表示原置换(输出任意一个)，否则输出-1

Sample Input

4
　　2 1 4 3

Sample Output

3 4 2 1

HINT

1<=n<=10^6

Main idea

已知一个置换置换自己得到的序列，求这个置换。

Solution

显然是置换题。首先我们正向考虑，考虑一下一个置换置换自己会发生怎样的结果。

然后我们一波画图发现：如果一个轮换的长度是奇数，那么这个环所有点连边向后移一位；如果一个轮换的长度数偶数，那么就会拆解成两个长度一样的新轮换。

然后我们倒着来想，考虑如何合并。显然现在的轮换是奇数的话，我们将所有点连边向前移动一位。如果是偶数的话，再找一个长度和这个一样的轮换，把两个轮换并在一起，并在一起就是两个轮换依次取出一个。

如果轮换是偶数且找不到一对的话就显然不合法。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;

const int ONE=1000005;

int n;
int x,P[ONE],d[ONE],record[ONE];
int vis[ONE],cnt,tot,num;
int Ans[ONE];

vector <int> q[ONE];
struct power
{
    int len;
    int id;
}R[ONE];
int cmp(const power &a,const power &b){return a.len < b.len;}

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

int main()
{
    n=get();
    for(int i=1;i<=n;i++) P[i]=get();

    for(int i=1;i<=n;i++)
    {
        if(vis[i]) continue;
        cnt = 0;    x = i;
        for(;;)
        {
            record[++cnt]=x;
            x = P[x];
            vis[x] = 1;
            if(x==i) break;
        }

        if(cnt==1) {Ans[i]=i; continue;}

        if(cnt%2==1)
        {
            int len=1;
            num=0;
            for(int j=1;j<=cnt;j++)
            {
                d[len]=record[j];
                len+=2;    if(len>cnt) len-=cnt;
            }
            d[cnt+1]=d[1];
            for(int j=1;j<=cnt;j++)  Ans[d[j]]=d[j+1];
        }
        else
        {
            R[++tot].id=tot;    R[tot].len=cnt;
            for(int j=1;j<=cnt;j++)
                q[tot].push_back(record[j]);
        }
    }

    if(tot%2==1) {printf("-1");exit(0);}
    sort(R+1,R+tot+1,cmp);

    for(int j=1;j<=tot;j+=2)
    {
        int x=R[j].id, y=R[j+1].id;
        if(R[j].len != R[j+1].len) {printf("-1");exit(0);}

        num=0;
        for(int i=0;i<R[j].len;i++)
            d[++num]=q[x][i], d[++num]=q[y][i];

        d[num+1]=d[1];
        for(int i=1;i<=num;i++) Ans[d[i]]=d[i+1];
    }

    for(int i=1;i<=n;i++) printf("%d ",Ans[i]);
}