53 D Physical Education

問題

長さnの数列a[i]とb[i]が与えられる。
b[i]を、隣り合う二項を入れ替えることを繰り返すことでb[i]をa[i]にしたい。

b[i]をa[i]にするような操作の列を、どれか一つ出力せよ。

制約条件

• 答えは必ず存在する。
• a[i]≦10^9
• n≦300

方針

バブルソートをシミュレートすればよい。

ソースコード

int n,a[300],b[300];
void run(){
	cin>>n;
	rep(i,n)cin>>a[i];
	rep(i,n)cin>>b[i];
	
	vi ans;
	for(int i=n-1;i>0;i--)if(a[i]!=b[i]){
		int p;
		for(p=i-1;a[i]!=b[p];p--);
		rep(j,i-p)ans.pb(p+j+1), ans.pb(p+j+2), swap(b[p+j], b[p+j+1]);
	}
	cout<<ans.size()/2<<endl;
	rep(i,ans.size()/2)cout<<ans[i*2]<<" "<<ans[i*2+1]<<endl;
}