代码

#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define Fo(i,a,b) for(int i=(a);i<(b);++i)
#define Fr(i,a,b) for(int i=(a);i<=(b);++i)
#define Fl(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
const int MX=100000100;

const int W=16,U=65535;
unsigned tmp[MX];
int cnt[U+100];
void sort(unsigned *x,int n)
{
	unsigned *y=tmp;
	Fo(k,0,2)
	{
		memset(cnt,0,sizeof(cnt));
		Fr(i,1,n)++cnt[x[i]>>(k*W)&U];
		Fr(i,1,U)cnt[i]+=cnt[i-1];
		Fl(i,n,1)y[cnt[x[i]>>(k*W)&U]--]=x[i];
		swap(x,y);
	}
}

评测结果