Codeforces Global Round 3 C. Crazy Diamond

リンク
https://codeforces.com/problemset/problem/1148/C
問題解
1 1 1とn n nの2つの位置が便利であることが容易に発見され、1 1 1は右半分のいずれかと交換することができ、n n nは左半分のいずれかと交換することができるので、私が構築した戦略は、左半分に交換したい数字について、まずn n nに交換させ、それから正しい位置に交換する方法を考えています.もしこの数字が今左半分にあるなら、私は直接n n nと交換させます.さもないと1 1 1と交換してからn nと交換することができます
コード#コード#

#include
#define maxn 300010
#define linf (1ll<<60)
#define iinf 0x3f3f3f3f
#define eps 1e-8
#define cl(x) memset(x,0,sizeof(x))
#define mod 998244353ll
#define mp(a,b) make_pair(a,b)
using namespace std;
typedef long long ll;
ll read(ll x=0)
{
	int c, f=1;
	for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;
	for(;isdigit(c);c=getchar())x=x*10+c-48;
	return f*x;
}
ll N, a[maxn], pos[maxn];
vector< pair<ll,ll> > ans;
void opt(ll x, ll y)
{
	ans.emplace_back(make_pair(x,y));
	swap(pos[a[x]],pos[a[y]]);
	swap(a[x],a[y]);
}
int main()
{
	N=read();
	ll i;
	for(i=1;i<=N;i++)
	{
		a[i]=read();
		pos[a[i]]=i;
	}
	for(i=2;i<=N/2;i++)
	{
		if(pos[i]<=N/2)
		{
			opt(pos[i],N);
			opt(N,i);
		}
		else
		{
			opt(pos[i],1);
			opt(1,N);
			opt(N,i);
		}	
	}
	for(;i<N;i++)
	{
		if(pos[i]<=N/2)
		{
			opt(pos[i],N);
			opt(N,1);
			opt(1,i);
		}
		else
		{
			opt(1,pos[i]);
			opt(1,i);
		}
		
	}
	if(a[1]!=1)opt(1,N);
	printf("%d
",ans.size());
	for(auto p:ans)
	{
		printf("%lld %lld
",p.first,p.second);
	}
	return 0;
}