记录编号	246606	评测结果	AAAAATTTTTE
题目名称	排序测试	最终得分	45
用户昵称	FoolMike	是否通过	未通过
代码语言	C++	运行时间	6.126 s
提交时间	2016-04-06 17:55:12	内存使用	23.18 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int maxn=2000010;
const int t[10]={1,10,100,1000,10000,100000,1000000,10000000};
int hash[10],a[2][maxn],n,i,j,w,ma=-99999999,l=1;
int next[maxn],head[21],tail[21],cnt;
bool x,y;

int getv(int x,int w){
	return 9+(x/t[w])%10;
}

int main()
{
	freopen("sorttest.in","r",stdin);
	freopen("sorttest.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++){
		scanf("%d",&a[0][i]);
		ma=max(ma,abs(a[0][i]));
	}
	x=0;
	while (l<=ma){
		y=!x;
		memset(head,0,sizeof(head));
		for (i=1;i<=n;i++){
			next[i]=0;
			j=getv(a[x][i],w);
			if (head[j]==0) head[j]=tail[j]=i;
				else tail[j]=next[tail[j]]=i;
		}
		cnt=0;
		for (i=0;i<20;i++)
		for (j=head[i];j!=0;j=next[j])
			a[y][++cnt]=a[x][j];
		l*=10;x=y;w++;
	}
	for (i=1;i<=n;i++) printf("%d ",a[x][i]);
	printf("\n");
	return 0;
}