代码

#include<bits/stdc++.h>
using namespace std;
#define reg register unsigned
#define IOSIZE 1048576
static char in[IOSIZE],*p=in,*pp,out[IOSIZE],*q=out,ch[20],*t=ch;
#define fok p!=pp
int read(int& x){
    x=0;
    while(fok&&*p<48)++p;
    while(fok&&*p>47)x=(x<<1)+(x<<3)+(*p++^48);
    return fok;
}
void write(int x){
    !x&&(*q++=48,0);
    while(x)*t++=x%10+48,x/=10;
    while(t!=ch)*q++=*--t;
}
void Put(char a[]){fwrite(out,1,q-out,stdout),fwrite(a,1,strlen(a),stdout),q=out;}
#define ri reg int
void basesort(int n,unsigned *a,unsigned *b){
    int r1[256],r2[256],r3[256],r4[256];
    #define Mem(K) memset(r##K,0,sizeof(r##K))
    Mem(1),Mem(2),Mem(3),Mem(4);
    ri *p,*E,tp=n>>3,tmp;
    for(p=a,E=a+n;p!=E;++p)
        ++r1[*p&255],++r2[*p>>8&255],++r3[*p>>16&255],++r4[*p>>24&255];
    for(ri i=1;i<256;++i)
        r1[i]+=r1[i-1],r2[i]+=r2[i-1],r3[i]+=r3[i-1],r4[i]+=r4[i-1];
    for(tmp=tp,p=a+n-1;tmp;--tmp)
        b[--r1[p[0]&255]]=p[0],b[--r1[p[-1]&255]]=p[-1],
        b[--r1[p[-2]&255]]=p[-2],b[--r1[p[-3]&255]]=p[-3],
        b[--r1[p[-4]&255]]=p[-4],b[--r1[p[-5]&255]]=p[-5],
        b[--r1[p[-6]&255]]=p[-6],b[--r1[p[-7]&255]]=p[-7],p-=8;
    switch(n&7){
        case 7:b[--r1[*p&255]]=*p,--p;case 6:b[--r1[*p&255]]=*p,--p;
        case 5:b[--r1[*p&255]]=*p,--p;case 4:b[--r1[*p&255]]=*p,--p;
        case 3:b[--r1[*p&255]]=*p,--p;case 2:b[--r1[*p&255]]=*p,--p;
        case 1:b[--r1[*p&255]]=*p,--p;
    }
    #define todo(A,B,k,P) for(tmp=tp,p=B+n-1;tmp;--tmp)\
        A[--r##k[p[0]>>P&255]]=p[0],A[--r##k[p[-1]>>P&255]]=p[-1],\
        A[--r##k[p[-2]>>P&255]]=p[-2],A[--r##k[p[-3]>>P&255]]=p[-3],\
        A[--r##k[p[-4]>>P&255]]=p[-4],A[--r##k[p[-5]>>P&255]]=p[-5],\
        A[--r##k[p[-6]>>P&255]]=p[-6],A[--r##k[p[-7]>>P&255]]=p[-7],\
        p-=8;\
    switch(n&7){\
        case 7:A[--r##k[*p>>P&255]]=*p,--p;case 6:A[--r##k[*p>>P&255]]=*p,--p;\
        case 5:A[--r##k[*p>>P&255]]=*p,--p;case 4:A[--r##k[*p>>P&255]]=*p,--p;\
        case 3:A[--r##k[*p>>P&255]]=*p,--p;case 2:A[--r##k[*p>>P&255]]=*p,--p;\
        case 1:A[--r##k[*p>>P&255]]=*p,--p;\
    }
    todo(a,b,2,8)
    todo(b,a,3,16)
    for(tmp=tp,p=b+n-1;tmp;--tmp)
        a[--r4[p[0]>>24]]=p[0],a[--r4[p[-1]>>24]]=p[-1],
        a[--r4[p[-2]>>24]]=p[-2],a[--r4[p[-3]>>24]]=p[-3],
        a[--r4[p[-4]>>24]]=p[-4],a[--r4[p[-5]>>24]]=p[-5],
        a[--r4[p[-6]>>24]]=p[-6],a[--r4[p[-7]>>24]]=p[-7],p-=8;
    switch(n&7){
        case 7:a[--r4[*p>>24]]=*p,--p;case 6:a[--r4[*p>>24]]=*p,--p;
        case 5:a[--r4[*p>>24]]=*p,--p;case 4:a[--r4[*p>>24]]=*p,--p;
        case 3:a[--r4[*p>>24]]=*p,--p;case 2:a[--r4[*p>>24]]=*p,--p;
        case 1:a[--r4[*p>>24]]=*p,--p;
    }
}
static unsigned int b[100000000],n;
void sort(unsigned *a,int n){
basesort(n,a,b);
}

评测结果