代码

#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
#define MP make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const int maxn=1e8+10,maxm=1e5,P=(1<<16)-1;

int cnt[maxm],tmp[maxn];

void sort(ui *a, int n) {
	for(int i=0;i<n;i++) cnt[a[i]&P]++;
	for(int i=1;i<=P;i++) cnt[i]+=cnt[i-1];
	for(int i=0;i<n;i++) tmp[cnt[a[i]&P]--]=a[i];
	CLR(cnt,0);
	for(int i=0;i<n;i++) cnt[a[i]>>16]++;
	for(int i=1;i<=P;i++) cnt[i]+=cnt[i-1];
	for(int i=n;i;--i) a[--cnt[tmp[i]>>16]]=tmp[i];
}
/*
int main(){
	ui a[10],n;
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	sort(a,n);
	for(int i=0;i<n;i++) printf("%d \n",a[i]);
}
*/

评测结果