【Foreign】置换 [数论][置换]

置换

Time Limit: 10 Sec  Memory Limit: 256 MB

Description

　　

Input

　　

Output

　　

Sample Input

　　4
　　2 1 4 3

Sample Output

　　3 4 2 1

HINT

　　1<=n<=10^6

Main idea

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

Solution

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

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

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

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

Code

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<vector>

 #include<cmath>

 using namespace std;

 const int ONE=;

 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=,Q=;char c;

         while( (c=getchar())< || c> )

         if(c=='-')Q=-;

         res=c-;

         while( (c=getchar())>= && c<= )

         res=res*+c-;

         return res*Q;

 }

 int main()

 {

         n=get();

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

         for(int i=;i<=n;i++)

         {

             if(vis[i]) continue;

             cnt = ;    x = i;

             for(;;)

             {

                 record[++cnt]=x;

                 x = P[x];

                 vis[x] = ;

                 if(x==i) break;

             }

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

             if(cnt%==)

             {

                 int len=;

                 num=;

                 for(int j=;j<=cnt;j++)

                 {

                     d[len]=record[j];

                     len+=;    if(len>cnt) len-=cnt;

                 }

                 d[cnt+]=d[];

                 for(int j=;j<=cnt;j++)  Ans[d[j]]=d[j+];

             }

             else

             {

                 R[++tot].id=tot;    R[tot].len=cnt;

                 for(int j=;j<=cnt;j++)

                     q[tot].push_back(record[j]);

             }

         }

         if(tot%==) {printf("-1");exit();}

         sort(R+,R+tot+,cmp);

         for(int j=;j<=tot;j+=)

         {

             int x=R[j].id, y=R[j+].id;

             if(R[j].len != R[j+].len) {printf("-1");exit();}

             num=;

             for(int i=;i<R[j].len;i++)

                 d[++num]=q[x][i], d[++num]=q[y][i];

             d[num+]=d[];

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

         }

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

 }