1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include<bits/stdc++.h>
#include<windows.h>
#define CLOCKS_PER_SEC ((clock_t)1000)
const int MAX_CHAR=256;
const int maxn=1e4+7;
using namespace std;
int ans=0;
void MergeSort(int *a,int l,int r){
if(l==r)return ;
int mid=(l+r)>>1;
MergeSort(a,l,mid);
MergeSort(a,mid+1,r);
int i=l,j=mid+1;
int *b=new int[r-l+10];
int tot=0;
while(i<=mid&&j<=r){
if(a[i]<=a[j]) b[tot++]=a[i++];
else {
ans+=mid-i+1;
b[tot++]=a[j++];
}
}
while(i<=mid) b[tot++]=a[i++];
while(j<=r) b[tot++]=a[j++];
tot=0;
while(l<=r)
a[l++]=b[tot++];
}
int main() {
int n,a[maxn];
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
MergeSort(a,0,n-1);
for(int i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n%d\n",ans);
return 0;
}
|
