记录编号	602335	评测结果	AAAAAAAAAA
题目名称	4166.遵循指令之意	最终得分	100
用户昵称	二乾五	是否通过	通过
代码语言	C++	运行时间	2.406 s
提交时间	2025-07-03 16:35:11	内存使用	11.37 MiB

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define cl(a) memset(a,0,sizeof a)
#define copy(a,b) copy(begin(a),end(a),begin(b))
#define ld long double
#define dot(x) fixed<<setprecision(x)
#define foru(a,b,c) for(ll a=b;a<=c;a++)

ll n,a[1000005],b[500005],c[500005],t[500005],bcnt,ccnt,ans,ans2;

void binarysortb(ll l,ll r){
    if(l>=r){
        return;
    }
    ll mid=(l+r)>>1;
    binarysortb(l,mid);
    binarysortb(mid+1,r);
    ll i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(b[i]<=b[j]){
            t[k++]=b[i++];
        }else{
            t[k++]=b[j++];
            ans+=mid-i+1;
        }
    }
    while(i<=mid){
        t[k++]=b[i++];
    }
    while(j<=r){
        t[k++]=b[j++];
    }
    for(ll i=l;i<=r;i++){
        b[i]=t[i];
    }
}

void binarysortc(ll l,ll r){
    if(l>=r){
        return;
    }
    ll mid=(l+r)>>1;
    binarysortc(l,mid);
    binarysortc(mid+1,r);
    ll i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(c[i]<=c[j]){
            t[k++]=c[i++];
        }else{
            t[k++]=c[j++];
            ans+=mid-i+1;
        }
    }
    while(i<=mid){
        t[k++]=c[i++];
    }
    while(j<=r){
        t[k++]=c[j++];
    }
    for(ll i=l;i<=r;i++){
        c[i]=t[i];
    }
}

int main(){
    #ifndef ONLINE_JUDGE
        freopen("sort.in" ,"r",stdin );
        freopen("sort.out","w",stdout);
    #endif
    cin>>n;
    foru(i,1,n)cin>>a[i];
    for(ll i=1;i<=n;i++){
        if(i%2==1){
            b[++bcnt]=a[i];
        }else{
            c[++ccnt]=a[i];
        }
    }
    binarysortb(1,bcnt);
    ans2=ans;
    ans=0;
    binarysortc(1,ccnt);
    if(abs(ans-ans2)&1){
        if(n%2){
            swap(b[bcnt-1],b[bcnt]);
        }else{
            swap(c[ccnt-1],c[ccnt]);
        }
    }
    foru(i,1,n){
        if(i%2==1){
            cout<<b[(i+1)/2]<<" ";
        }else{
            cout<<c[i/2]<<" ";
        }
    }
    return 0;
}