TopCoder SRM 765 : Div1 Easy Div2 Hard FixedPointReversals

Easyはそこそこの速度で解いたけど、Mediumを落としてレート減。
https://community.topcoder.com/stat?c=problem_statement&pm=15693

問題

N要素の数列Aが与えられる。
区間を設定してその間を反転させる、という処理を1.5*N回以下行い、数列をソートしたい。
なお、ここで不動点が1個設定させる。
処理の過程でこの要素は動かしてはならない。
条件を満たす手順を求めよ。

解法

まずAを普通にソートし、不動点におけるソート前後の値が変更不要かを求めておこう。
この時点で変更要なら、解なし。

そうでない場合、まず各要素について行先を決める。
以後、以下の3ステップで実行する。

• 不動点より前にある要素のうち、不動点の後に持っていきたいものを不動点寄りに寄せる。
• 不動点より後ろにある要素のうち、不動点の前に持っていきたいものを不動点寄りに寄せる。

上記要素の数は等しい。よって、不動点を中心に入れ替えたい要素数だけ前後に広い範囲を反転しよう。
そうすると不動点を動かすことなく、不動点の前・後ろに持ってきたい要素は、全て前・後ろにそろった。

あとは不動点の前と後ろそれぞれの内部で、端から値をそろえていけばよい。

class FixedPointReversals {
	public:
	vector<int> C;
	vector<int> ret;
	void goswap(int a,int b) {
		ret.push_back(a);
		ret.push_back(b+1);
		reverse(C.begin()+a,C.begin()+b+1);
	}
	vector <int> sort(vector <int> A, int F) {
		int N=A.size();
		vector<int> B=A;
		C.resize(N);
		ret.clear();
		
		std::sort(ALL(B));
		if(A[F]!=B[F]) return {-1};
		
		int x,y,i;
		C[F]=F;
		FOR(x,N) if(x!=F) {
			FOR(y,N) if(y!=F && A[y]==B[x]) {
				C[y]=x;
				A[y]=-1;
				break;
			}
		}
		
		
		while(1) {
			int L,R;
			FOR(L,F) if(C[L]>F) break;
			for(R=F-1;R>=0;R--) if(C[R]<F) break;
			
			if(L>=R) break;
			goswap(L,R);
		}
		while(1) {
			int L,R;
			for(L=F+1;L<N;L++) if(C[L]>F) break;
			for(R=N-1;R>F;R--) if(C[R]<F) break;
			
			if(L>=R) break;
			goswap(L,R);
		}
		
		int num=0;
		FOR(i,F) if(C[i]>F) num++;
		if(num) {
			goswap(F-num,F+num);
		}
		FOR(i,F) if(C[i]!=i) {
			for(x=i+1;x<F;x++) if(C[x]==i) break;
			goswap(i,x);
		}
		
		for(i=F+1;i<N;i++) if(C[i]!=i) {
			for(x=i+1;x<N;x++) if(C[x]==i) break;
			goswap(i,x);
		}
		
		return ret;
		
		
	}
}

まとめ

意外に落ちてたけどどこが罠だったんだろうな。