TopCoderOpen 2019 Wildcard Easy FilmSort

これは不参加でした。
https://community.topcoder.com/stat?c=problem_statement&pm=15689

問題

N要素の数列が与えられる。
各要素は負の数もあり、絶対値は0～(N-1)のPermutationとなっている。

この数列を全要素非負でかつ昇順にソートされた状態にしたい。
以下の処理を5N回以下で行ってソートせよ。

• 非ゼロの要素を選択し、ゼロの要素と位置を入れ替える。その際非ゼロの値は符号が反転する。

解法

まず符号は無視して絶対値が昇順になるように並べ替える。
これは端から順にソートしよう。たとえば、以下のような状態でaを左端に持っていきたいとする。
b...0....a　→ 0...-b...a → -a...b...0
符号を無視すればこのように2手で値を任意に移動できる。

次に符号をそろえることを考える。
符号が負の要素を2つ選ぶと、0を含めた3要素を2手で符号反転しつつローテートできるので、これを3回繰り返す。
0...-a...-b → a...0...-b → a...b...0 → 0...b...-a → -b...0...-a → -b...a...0 → 0...a...b

合わせると1個の位置と符号を合わせるのに最大5手なので、5N回以下の処理回数で済む。

class FilmSort {
	public:
	vector<int> R,V;
	int N;
	void go(int x,int y) {
		if(x==y) return;
		if(R[x]==0) {
			V.push_back(y);
		}
		else {
			V.push_back(x);
		}
		swap(R[x],R[y]);
		R[x]=-R[x];
		R[y]=-R[y];
	}
	
	
	vector <int> sort(vector <int> reels) {
		R=reels;
		int N=R.size();
		V.empty();
		
		int i,j,x;
		
		for(i=1;i<N;i++) if(abs(R[i])!=i) {
			FOR(j,N) if(abs(R[j])==0) {
				go(i,j);
				break;
			}
			FOR(j,N) if(abs(R[j])==i) {
				go(i,j);
				break;
			}
		}
		FOR(i,N) cout<<R[i]<<" ";
		cout<<endl;
		for(i=1;i<N;i++) if(R[i]<0) {
			for(j=i+1;j<N;j++) if(R[j]<0) {
				go(i,0);
				go(j,i);
				go(j,0);
				go(i,0);
				go(j,i);
				go(j,0);
				break;
			}
			if(j==N) return {-1};
		}
		
		return V;
		
	}
}

まとめ

問題文がわかりにくかった。
フィルムとかリールとか言わず、数列云々言ってくれた方がよかったな。