代码

#include<bits/stdc++.h>
using namespace std;
#define int unsigned
const int siz1=9,len1=4e5,siz2=9,len2=1000,siz3=8,len3=20;
int a[(1<<siz1)*len1+10],b[(1<<siz2)*len2+10],c[(1<<siz3)*len3+10];
int *p1[1<<siz1],*p2[1<<siz2],*p3[1<<siz3];
void sort(int *arr,signed n)
{
	for(int i=0; i<(1<<siz1); ++i) p1[i]=a+i*len1;
	for(int i=0; i<n; ++i) (*p1[arr[i]>>32-siz1]++)=arr[i];
	int now=0;
	for(int i=0; i<(1<<siz1); ++i)
	{
		for(int j=0; j<(1<<siz2); ++j) p2[j]=b+j*len2;
		int *wz=a+i*len1;
		while(wz!=p1[i]) (*p2[((*wz)&((1<<32-siz1)-1))>>32-siz1-siz2]++)=*wz,++wz;
		for(int j=0; j<(1<<siz2); ++j)
		{
			for(int k=0; k<(1<<siz3); ++k) p3[k]=c+k*len3;
			int *wz=b+j*len2;
			while(wz!=p2[j]) (*p3[((*wz)&((1<<32-siz1-siz2)-1))>>32-siz1-siz2-siz3]++)=*wz,++wz;
			for(int k=0; k<(1<<siz3); ++k)
			{
				sort(c+k*len3,p3[k]);
				memcpy(arr+now,c+k*len3,(p3[k]-c-k*len3)*4),now+=p3[k]-c-k*len3;
			}
		}
	}
}

评测结果