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

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
int n,a[N],ans[N],ji1[N],ou1[N],so=0,sj=0;
int ji[N],ou[N],jz=0,oz=0;
void nxdji(int l,int r)
{
	if(l==r) return;
	int m=(l+r)/2;
	nxdji(l,m);
	nxdji(m+1,r);
	int i=l,j=m+1;
	int cnt=l;
	while(i<=m||j<=r){
		if(j>r) ji1[cnt++]=ji[i++];
		else if(i>m)
			ji1[cnt++]=ji[j++];
		else if(ji[i]<=ji[j])
			ji1[cnt++]=ji[i++];
		else{
			ji1[cnt++]=ji[j++];
			sj+=(m-i+1);
		}
	}
	for(int i=l;i<=r;i++) ji[i]=ji1[i];
}
void nxdou(int l,int r)
{
	if(l==r) return;
	int m=(l+r)/2;
	nxdou(l,m);
	nxdou(m+1,r);
	int i=l,j=m+1;
	int cnt=l;
	while(i<=m||j<=r){
		if(j>r) ou1[cnt++]=ou[i++];
		else if(i>m)
			ou1[cnt++]=ou[j++];
		else if(ou[i]<=ou[j])
			ou1[cnt++]=ou[i++];
		else{
			ou1[cnt++]=ou[j++];
			so+=(m-i+1);
		}
	}
	for(int i=l;i<=r;i++) ou[i]=ou1[i];
}
int main()
{
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        if(i%2==0) ou[++oz]=a[i];
        else if(i%2==1) ji[++jz]=a[i];
    }
    nxdji(1,jz);
    nxdou(1,oz);
    sort(ji+1,ji+jz+1);
    sort(ou+1,ou+oz+1);
    jz=0,oz=0;
    for(int i=1;i<=n;i++){
        if(i%2==1){
            jz++;
            ans[i]=ji[jz];
        }
        else if(i%2==0){
            oz++;
            ans[i]=ou[oz];
        }
    }
    if(so%2!=sj%2) swap(ans[n],ans[n-2]);
    for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
    cout<<endl;
    return 0;
}