代码

#include<stdio.h>
using namespace std;

char file[30000001];

int n,a[200001],b[200001],c1[200001],c2[200001];
const int hf=46341;

inline int getchar() {
	static int now=0;
	return file[now++];
}

inline void read_int(int &a) {
	static int c;
	c=getchar();a=0;
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') a=(a<<1)+(a<<3)-48+c,c=getchar();
}

int main() {
	fread(file,sizeof(char),30000000,stdin);
	
	read_int(n);
	
	for (int i=1;i<=n;i++) {
		read_int(a[i]);
		++c1[a[i]/hf];++c2[a[i]%hf];
	}
	
	for (int i=1;i<hf;i++)
		c1[i]+=c1[i-1],c2[i]+=c2[i-1];
	
	for (int i=n;i>=1;i--)
		b[c2[a[i]%hf]--]=a[i];
	for (int i=n;i>=1;i--)
		a[c1[b[i]/hf]--]=b[i];
	
	for (int i=1;i<=n;i++)
		printf("%d\n",a[i]);
	return 0;
}

评测结果