代码

#include<bits/stdc++.h>
#define REP(i,first,last) for(register int i=(first);i<=(last);++i)
#define DOW(i,first,last) for(register int i=(first);(last)<=i;--i)
#define LL long long
#define UI unsigned int
#define ULL unsigned long long
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLI pair<long long,int>
#define PLL pair<long long,long long>
#define MPR(a,b) make_pair(a,b)
#define CLEAN(a) memset(a,0,sizeof(a))
#define COVER(a,v) memset(a,v,sizeof(a))
#define SURVEILLANCE(type_name) IO::DeBugln("On line ",__LINE__," "#type_name"=",type_name)
const int MAXN=1e8+5;
const int W=1e5;
unsigned b[MAXN];
int sum[W+5];
int cnt[W+5];
inline void Sort(unsigned *a,int n)
{
	for(register int i(0);i<n;++i)
	{
		++sum[a[i]%W];
	}
	REP(i,1,W)
	{
		sum[i]+=sum[i-1];
		cnt[i]=sum[i-1];
	}
	for(register int i(0);i<n;++i)
	{
		b[cnt[a[i]%W]++]=a[i];
	}
	memcpy(a,b,sizeof(b));
	CLEAN(sum);
	for(register int i(0);i<n;++i)
	{
		++sum[a[i]/W];
	}
	cnt[0]=0;
	REP(i,1,W)
	{
		sum[i]+=sum[i-1];
		cnt[i]=sum[i-1];
	}
	for(register int i(0);i<n;++i)
	{
		b[cnt[a[i]/W]++]=a[i];
	}
	memcpy(a,b,sizeof(b));
}

评测结果