Codeforces Global Round 9 : E. Inversion SwapSort

ビハインドが9か月になろうとしている…。
https://codeforces.com/contest/1375/problem/E

問題

整数列Aが与えられる。
この整数列を、2要素のswapを行いソートしたい。
その時、以下の条件を満たす必要がある。

• 同じ位置のペアは、1回しかswapできない。
• もともとinversionを起こしていた位置のペアは1回ずつswapしなければならず、inversionでない部分はswapしてはならない。

条件を満たすものを求めよ。

解法

元の値の小さい順に処理をしていく。
もし現在位置の右側に、自分より小さい値=inversionを起こしているものがあれば、右側から順にswapを行う。
そうすると、自身と、右側にある自分より小さい値のみに関し左に1個rotateした状態になる。
これは、言い換えると自分より小さい値の相対的な位置を変えずに、自身をより小さい値の右側に持っていけることに相当する。

int N;
int A[1010];
int S[1010][1010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	map<int,vector<int>> M;
	FOR(i,N) {
		cin>>A[i];
		M[A[i]].push_back(i);
	}
	vector<pair<int,int>> R;
	vector<int> C;
	FORR(m,M) {
		vector<int> B=m.second;
		reverse(ALL(C));
		FORR(b,B) FORR(c,C) if(b<c) {
			R.push_back({b,c});
		}
		FORR(b,B) C.push_back(b);
		sort(ALL(C));
		
	}
	
	
	cout<<R.size()<<endl;
	FORR(r,R) cout<<r.first+1<<" "<<r.second+1<<endl;
	
}

まとめ

競技プログラミング関係者、いろんなソート考えすぎじゃないですか。