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

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],o[N],e[N],res[N],f[N],n;
int lowbit(int x){
    return x&(-x);
}
int ask(int x){
    int ans=0;
    for(;x;x-=lowbit(x)) ans+=f[x];
    return ans;
}
void add(int x,int y){
    for(;x<=n;x+=lowbit(x)) f[x]+=y;
}
int main(){
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); 
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int ol=0,el=0;
    for (int i=1;i<=n;++i) {
        if (i%2==1) {
            o[++ol]=a[i];
        }else{
            e[++el]=a[i];
        }
    }
    int cnto=0,cnte=0;
    memset(f,0,sizeof(f));
    for(int i=ol;i;i--){
        add(o[i],1);
        cnto+=ask(o[i]-1);
    }
    memset(f,0,sizeof(f));
    for(int i=el;i;i--){
        add(e[i],1);
        cnte+=ask(e[i]-1);
    }
    sort(o+1,o+ol+1);
    sort(e+1,e+el+1);
    ol=0,el=0;
    for(int i=1;i<=n;++i) {
        if (i%2==1) {
            res[i]=o[++ol];
        }else{
            res[i]=e[++el];
        }
    }
    if(cnte%2!=cnto%2){
        swap(res[n],res[n-2]);
    }
    for(int i=1;i<=n;i++) cout<<res[i]<<' ';
    return 0;
}