这一题要求对$10^6$个小于$10^{18}$的正整数排序，时限200ms，空间512MiB。

思路：把每个数按$2^{20}$拆分，再进行多关键字基数排序

代码：

#include<cstdio>
const long long rm=20,M=(1<<rm)-1;
const int size=21000000;
long long arr[1000500],tmp[1000500],*head[1000500],*cur=tmp,*lst=arr,*temp;
int n,m,cnt[1000500],w,pr;
long long a;
static char buff[size],buf[size],st[25];
inline char gc(){
	static char *p1=buf+size,*p2=buf+size;
	if(p1==p2)p2=(p1=buf)+fread(buf,1,size,stdin);
	return p1==p2?-1:*p1++;
}
inline long long ge(){
	char ch=0;
	long long sum=0;
	while(!(ch>='0'&&ch<='9'))ch=gc();
	while(ch>='0'&&ch<='9')sum=(sum<<3)+(sum<<1)+ch-'0',ch=gc();
	return sum;
}
inline void out(long long a){
    int p=0;
    for(;a!=0;a/=10)st[p++]=a%10+'0';
    for(int i=p-1;i>=0;i--)buff[pr++]=st[i];
    buff[pr++]='\n';
}
inline void flush(){
	buff[pr]=0;
	fputs(buff,stdout);
}
int main(){
	freopen("a.txt","r",stdin);
	freopen("1.txt","w",stdout);
    n=ge();
	for(int i=0;i<n;i++)arr[i]=ge(),printf("%lld\n",arr[i]);
    for(int i=0;i<=2;i++){
    	printf("%d\n",i);
    	w=(i<<4)+(i<<2);
    	printf("%d\n",w);
	    for(int j=0;j<n;j++)cnt[(lst[j]>>w)&M]++;
	    printf("svvf\n");
	    head[0]=cur;
	    printf("svvf\n");
	    for(int j=1;j<=M;j++)head[j]=head[j-1]+cnt[j-1],cnt[j-1]=0;
	    printf("svvf\n");
	    for(int j=0;j<n;j++)*(head[(lst[j]>>w)&M]++)=lst[j],printf("%d %lld\n",j,*(head[(lst[j]>>w)&M]-1));
	    printf("svvf\n");
	    temp=cur,cur=lst,lst=temp;
	}
	if(lst!=arr)for(int i=0;i<n;i++)arr[i]=lst[i];
    for(int i=0;i<n;i++)out(arr[i]);
    flush();
    return 0;
}

样例：

10
217280184211540919
217280611943329677
634943297893368815
446437510777852490
279041087446598816
634942999163711373
698687070108168924
267945954914599702
338575905611448855
574066836207216204

目测在for(int i=0;i<=2;i++)的for(int j=0;j<n;j++)*(head[(lst[j]>>w)&M]++)=lst[j],printf("%d %lld\n",j,*(head[(lst[j]>>w)&M]-1));处re，暂不知道原因。