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

#include<bits/stdc++.h>
using namespace std;
int n,a[1000001],b[1000001],c[1000001],r1[1000001],r2[1000001],ans,ans2;
int myceil(int a,int b){
	if(a%b==0){
		return a/b;
	}
	else{ 
		return a/b+1;
	}
}
void msort1(int s,int e){
	if(s==e){
		return; 
	}
	int mid=(s+e)/2;
	msort1(s,mid);
	msort1(mid+1,e);
	int i=s,j=mid+1,k=s;
	while(i<=mid&&j<=e){
		if(b[i]<=b[j]){
			r1[k]=b[i];
			k++;
			i++;
		}
		else{
			r1[k]=b[j];
			k++;
			j++;
			ans+=mid-i+1;
		}
	} 
	while(i<=mid){
		r1[k]=b[i];
		k++;
		i++;
	} 
	while(j<=e){
		r1[k]=b[j];
		k++;
		j++;
	} 
	for(int i=s;i<=e;i++){
		b[i]=r1[i];
	}
	return;
}
void msort2(int s,int e){
	if(s==e){
		return; 
	}
	int mid=(s+e)/2;
	msort2(s,mid);
	msort2(mid+1,e);
	int i=s,j=mid+1,k=s;
	while(i<=mid&&j<=e){
		if(c[i]<=c[j]){
			r2[k]=c[i];
			k++;
			i++;
		}
		else{
			r2[k]=c[j];
			k++;
			j++;
			ans2+=mid-i+1;
		}
	} 
	while(i<=mid){
		r2[k]=c[i];
		k++;
		i++;
	} 
	while(j<=e){
		r2[k]=c[j];
		k++;
		j++;
	} 
	for(int i=s;i<=e;i++){
		c[i]=r2[i];
	}
	return;
}
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++){
		int q=myceil(i,2);
		if(i%2==1){
			b[q]=a[i];
		}
		else{
			c[q]=a[i];
		}
	}
	msort1(1,n/2+(n%2));
	msort2(1,n/2);
//	cout<<ans<<" "<<ans2<<endl;
	for(int i=1;i<=n;i++){
		int q=myceil(i,2);
		if(i%2==1){
			a[i]=b[q];
		}
		else{
			a[i]=c[q];
		}
	}
	if(ans%2!=ans2%2){
		swap(a[n-2],a[n]);
	}
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}