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

#include <bits/stdc++.h>
#define N 1000005
using namespace std;
int n, tree[N], a[N >> 1], b[N >> 1], arr[N], acnt, bcnt, cnt;
int ansarr, ansa, ansb;
void add(int x, int y) {
  for (; x <= N - 5; x += (x & -x)) tree[x] += y;
}
int ask(int x) {
  int res = 0;
  for (; x; x -= (x & -x)) res += tree[x];
  return res;
}
void work(int arr[], int len, int &ans) {
    memset(tree, 0, sizeof(tree));
    ans = 0;
    for(int i = len; i >= 1; i--) {
        ans += ask(arr[i] - 1);
        add(arr[i], 1);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    freopen("sort.in", "r", stdin);
    freopen("sort.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        if (i & 1) {
            a[++acnt] = arr[i];
        } else {
            b[++bcnt] = arr[i];
        }
    }
    work(arr, n, ansarr);
    work(a, acnt, ansa);
    work(b, bcnt, ansb);
    sort(a + 1, a + acnt + 1);
    sort(b + 1, b + bcnt + 1);
    for(int i = 1;i <= bcnt; i++) {
        arr[++cnt] = a[i];
        arr[++cnt] = b[i];
    }
    if(acnt > bcnt) arr[++cnt] = a[acnt];
    if((ansa & 1) != (ansb & 1)) swap(arr[cnt], arr[cnt - 2]);
    for (int i = 1; i <= cnt; ++i) cout << arr[i] << " \n"[i == cnt];
    return 0;
}