Codeforces ECR #004 : E. Square Root of Permutation

一瞬yukicoderの直列あみだくじが思い浮かんだ。
http://codeforces.com/contest/612/problem/E

問題

1～Nのpermutationである数列Q[i] (1-origin)がある。
P[i]=Q[Q[i]]で定義される数列Pが与えられている。
そのようなPを構築するQが存在すればそれを答えよ。

解法

1～Nのうち未処理の整数xに対し、x→P[x]→P[P[x]]→…→P^k[x]=xとなる巡回列を求めよう。

• kが奇数の時
  • Q[x]=P^((k+1)/2)[x]とすると、Q[Q[x]]=P^(k+1)[x]=P[x]となる。よって上記巡回列中に登場するy=P^i[x]については、それぞれQ[y]=P^(k+1)[y]とおいてよい良い。
• kが偶数の時
  • 同じ長さの別の巡回列y→P[y]→P[P[y]]→…→P^k[y]=yを求めよう。
  • Q[x]=y、Q[y]=P[x]、となるように、Qを両順列の値を交互に取るような巡回列とすればよい。

元のPにおいて、kが偶数の巡回列は登場回数が偶数でないと条件を満たすQが作れないことに注意。

int N;
int A[1001000],C[1001000];
int used[1010101];
vector<int> R[1010100];
int rem[1010100];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(i,N) cin>>A[i], A[i]--;
	MINUS(C);
	MINUS(rem);
	
	FOR(i,N) if(C[i]==-1) {
		x=i;
		while(x!=i || R[i].empty()) {
			C[x]=-2;
			R[i].push_back(x);
			x=A[x];
		}
		r=R[i].size();
		if(r%2==1) {
			FOR(j,r) C[R[i][j]]=R[i][(j+r/2+1)%r];
		}
		else {
			if(rem[r]==-1) rem[r]=i;
			else {
				y=rem[r];
				FOR(j,r) {
					C[R[y][j]]=R[i][j];
					C[R[i][j]]=R[y][(j+1)%r];
				}
				rem[r]=-1;
			}
		}
	}
	
	FOR(i,N) if(C[i]<0) return _P("-1\n");
	FOR(i,N) _P("%d ",C[i]+1);
	_P("\n");
	
}

まとめ

最初直列あみだくじのコード貼って終了かと思ったら、当時O(N^2)のコードを書いてたのでダメだった。