Codeforces Global Round 13 : G. Switch and Flip

気付いてしまえば簡単なんだけどね。
https://codeforces.com/contest/1491/problem/G

問題

1～Nのコインがそれぞれ表向きである順で並んでいる。
以下の処理を(N+1)回以下行い、1～Nの順で表向きで並ぶようにせよ。

• 2枚のコインを選びその位置を入れ替える。その際、いずれも表裏反転する。

解法

コインの現在位置と置くべき位置の関係を考えると、いくつかの閉路からなるfunction graphになる。
長さ2以上の2つの閉路について、初手で両閉路の1要素ずつをswapするようにすると、全体を閉路長の和分で正しい位置に移動させることができる。
もし最後に長さ2以上の閉路が1個残った場合、(閉路長+1)手使い並べ替えよう。
もし閉路の長さが2なら、閉路外の要素を1個使い達成することができるし、閉路の長さが3以上なら、閉路内だけで並べ替えを達成できる。

int N;
int C[202020];
int vis[202020];
vector<vector<int>> P;
vector<pair<int,int>> R;

void add(int& a,int& b) {
	R.push_back({a,b});
	swap(C[a],C[b]);
	C[a]=-C[a];
	C[b]=-C[b];
}

void go_single(vector<int> P) {
	int N=P.size();
	
	
	if(N==2) {
		int tar=1;
		while(tar==P[0]||tar==P[1]) tar++;
		R.push_back({P[0],tar});
		R.push_back({P[1],tar});
		R.push_back({P[0],tar});
		
	}
	else {
		add(P[N-2],P[N-1]);
		add(P[N-3],P[N-1]);
		for(int i=0;i<N-2;i++) add(P[i],P[N-2]);
		add(P[N-2],P[N-1]);
		
	}
}

void go_twin(vector<int> A,vector<int> B) {
	int N=A.size();
	int M=B.size();
	deque<int> P,Q;
	FORR(a,A) P.push_back(a);
	FORR(a,B) Q.push_back(a);
	
	
	add(P.back(),Q.back());
	while(Q.size()>1) {
		add(P.back(),Q[0]);
		Q.pop_front();
	}
	while(P.size()>1) {
		add(Q.back(),P[0]);
		P.pop_front();
	}
	add(P[0],Q[0]);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>C[i+1];
	
	for(i=1;i<=N;i++) if(vis[i]==0) {
		vector<int> A;
		x=i;
		while(vis[x]==0) {
			A.push_back(x);
			vis[x]=1;
			x=C[x];
		}
		if(A.size()>1) P.push_back(A);
	}
	
	while(P.size()>=2) {
		go_twin(P[P.size()-1],P[P.size()-2]);
		P.pop_back();
		P.pop_back();
	}
	
	if(P.size()) go_single(P[0]);
	
	//FOR(i,N) cout<<C[i+1];
	//cout<<endl;
	cout<<R.size()<<endl;
	FORR(r,R) cout<<r.first<<" "<<r.second<<endl;
	
}

まとめ

こっちを先に解けばよかったな。