记录编号	602280	评测结果	AAAAAAAAAA
题目名称	4166.遵循指令之意	最终得分	100
用户昵称	Ruyi	是否通过	通过
代码语言	C++	运行时间	2.387 s
提交时间	2025-07-03 14:27:40	内存使用	7.17 MiB

#include<bits/stdc++.h>
#define ll long long
#define N 500001
using namespace std;
ll n,m,e[N],o[N];
bool t[N*2],sum;
void ud(int x){
    while(x<=n){
        t[x]=!t[x];
        x+=x&-x;
    }
}
bool gs(int x){
    bool sum=0;
    while(x){
        sum^=t[x];
        x&=x-1;
    }
    return sum;
}
int main(){
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    cin>>n;
    m=n>>1;
    for(int i=1;i<=m;i++) cin>>e[i]>>o[i];
    if(n&1) cin>>e[m+1];
    if(n<4){
        for(int i=1;i<=m;i++) cout<<e[i]<<' '<<o[i]<<' ';
        if(n&1) cout<<e[m+1]<<endl;
        return 0;
    }
    if(n&1) m++;
    for(int i=m;i;i--){
        sum^=gs(e[i]);
        ud(e[i]);
    }
    for(int i=1;i<=n;i++) t[i]=0;
    sort(e+1,e+m+1);
    if(n&1) m--;
    for(int i=m;i>0;i--){
        sum^=gs(o[i]);
        ud(o[i]);
    }
    sort(o+1,o+m+1);
    if(sum){
        if(n&1) swap(e[m],e[m+1]);
        else swap(o[m-1],o[m]);
    }
    for(int i=1;i<=m;i++) cout<<e[i]<<' '<<o[i]<<' ';
    if(n&1) cout<<e[m+1]<<endl;
    return 0;
}