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

#include<iostream>
#include<cstring>
using namespace std;

#define ll long long
const int MAXN = 1000005;

ll n;
ll a[MAXN];
ll odd[MAXN], even[MAXN];
ll tot1 = 0, tot2 = 0;
ll ans1 = 0, ans2 = 0;

void merge1(ll l, ll mid, ll r){
    ll i = l, j = mid + 1, k = 0;
    ll tmp[r - l + 1];
    while(i <= mid && j <= r){
        if (odd[i] <= odd[j]){
            tmp[k ++] = odd[i ++];
        }
		else{
            tmp[k ++] = odd[j ++];
            ans1 += mid - i + 1;
        }
    }
    while(i <= mid){
        tmp[k ++] = odd[i ++];
    }
    while(j <= r){
        tmp[k ++] = odd[j ++];
    }
    for(i = l, k = 0;i <= r;i ++, k ++){
        odd[i] = tmp[k];
    }
}

void qsort1(ll l, ll r){
    if (l >= r) return;
    ll mid = (l + r) / 2;
    qsort1(l, mid);
    qsort1(mid + 1, r);
    merge1(l, mid, r);
}

void merge2(ll l, ll mid, ll r){
    ll i = l, j = mid + 1, k = 0;
    ll tmp[r - l + 1];
    while(i <= mid && j <= r){
        if(even[i] <= even[j]){
            tmp[k ++] = even[i ++];
        }
		else {
            tmp[k ++] = even[j ++];
            ans2 += mid - i + 1;
        }
    }
    while(i <= mid){
        tmp[k ++] = even[i ++];
    }
    while(j <= r){
        tmp[k ++] = even[j ++];
    }
    for(i = l, k = 0; i <= r;i ++, k ++){
        even[i] = tmp[k];
    }
}

void qsort2(ll l, ll r){
    if (l >= r) return;
    ll mid = (l + r) / 2;
    qsort2(l, mid);
    qsort2(mid + 1, r);
    merge2(l, mid, r);
}

int main(){
	freopen("sort.in", "r", stdin);
	freopen("sort.out", "w", stdout);
    cin >> n;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
        if (i % 2 == 0){
            even[++ tot2] = a[i];
        }
		else{
            odd[++ tot1] = a[i];
        }
    }
    qsort1(1, tot1);
    qsort2(1, tot2);
    int index1 = 0, index2 = 0;
    if((ans1 % 2) == (ans2 % 2)){
    	for(int i = 1;i <= n;i ++){
			if(i % 2){
				cout << odd[++ index1] << ' ';
			}
			else{
				cout << even[++ index2] << ' ';
			}
		}
	}
	else{
		for(int i = 1;i <= n;i ++){
			if(i % 2){
				a[i] = odd[++ index1];
			}
			else{
				a[i] = even[++ index2];
			}
		}
		swap(a[n], a[n - 2]);
		for(int i = 1;i <= n;i ++){
			cout << a[i] << ' ';
		}
	}
    return 0;
}