Codeforces Global Round 3 : C. Crazy Diamond

この回はBを落として大打撃を受けた回。
https://codeforces.com/contest/1148/problem/C

問題

偶数長のPermutationが与えられる。
2つの要素をswapすることを繰り返し、この数列をソートしたい。
なお、その際swap対象の要素間の位置は、数列長の半分以上でなければならない。

解法

中心から順にそろえていく。

• もし数列の前半分にいるものを前半分の別の場所に動かす場合、いったん末尾に動かして目標の場所に動かす。
• もし数列の後ろ半分にいるものを前半分の別の場所に動かす場合、先頭→末尾と動かし、目標の場所に動かす。

後ろ半分に動かすときも同様。

int N;
int P[303030];
int R[303030];
vector<pair<int,int>> V;

void hoge(int x,int y) {
	assert(abs(x-y)>=N/2);
	if(x>y) swap(x,y);
	swap(P[x],P[y]);
	R[P[y]]=y;
	R[P[x]]=x;
	V.push_back({x,y});
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<=N;i++) {
		cin>>P[i];
		R[P[i]]=i;
	}
	vector<int> C;
	FOR(i,N/2) {
		C.push_back(N/2-i);
		C.push_back(N/2+1+i);
	}
	FORR(c,C) {
		if(c<=N/2) {
			if(R[c]>=N/2+1) hoge(1,R[c]);
			hoge(R[c],N);
			hoge(c,R[c]);
		}
		else {
			if(R[c]<=N/2) hoge(R[c],N);
			hoge(1,R[c]);
			hoge(c,R[c]);
		}
	}
	
	_P("%d\n",V.size());
	FORR(v,V) _P("%d %d\n",v.first,v.second);
}

まとめ

これはあまり迷わなかったね。