记录编号	602299	评测结果	AAAAAAAAAA
题目名称	4166.遵循指令之意	最终得分	100
用户昵称	rb_tree	是否通过	通过
代码语言	C++	运行时间	1.474 s
提交时间	2025-07-03 15:20:58	内存使用	6.77 MiB

#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x=0,w=1;
	char ch=0;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*w;
}
void write(int x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>=10) write(x/10);
	putchar((x%10)^48);
}
const int N=500005;
int cnta,cntb,ans,aa[N],bb[N],t[N],ans1[N],ans2[N],a[N];
void merge_sort(int l,int r)
{
    if(l==r) return;
    int mid=l+r>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    for(int i=l,j=l,k=mid+1;i<=r;i++)
    {
        if(j==mid+1) t[i]=a[k++];
        else if(k==r+1) t[i]=a[j++],ans+=k-mid-1;
        else if(a[j]<=a[k]) t[i]=a[j++],ans+=k-mid-1;
        else t[i]=a[k++];
    }
    for(int i=l;i<=r;i++) a[i]=t[i];
}
signed main()
{
    int n=read();
    for(int i=1;i<=n;i++)
    {
        if(i&1) aa[++cntb]=read();
        else bb[++cnta]=read();
    }
    for(int i=1;i<=cnta;i++) a[i]=aa[i];
    merge_sort(1,cnta);
    for(int i=1;i<=cnta;i++) aa[i]=a[i];
    for(int i=1;i<=cntb;i++) a[i]=bb[i];
    merge_sort(1,cntb);
    for(int i=1;i<=cntb;i++) bb[i]=a[i];
    const int as=cnta,bs=cntb;
    if(ans&1)
    {
        if(n&1) swap(aa[as],aa[as-1]);
        else swap(bb[bs],bb[bs-1]);
    }
    cnta=cntb=0;
    for(int i=1;i<=n;i++)
    {
        if(i&1) write(aa[++cnta]);
        else write(bb[++cntb]);
        putchar(' ');
    }
    return 0;
}