UVA - 11462:Age Sort

Age Sort
出典:UVA
ラベル:
参考資料:
類似タイトル:
タイトル
You are given the ages (in years) of all people of a country with at least 1 year of age. You know that no individual in that country lives for 100 or more years. Now, you are given a very simple task of sorting all the ages in ascending order.
入力
There are multiple test cases in the input file. Each case starts with an integer n (0 < n ≤ 2000000), the total number of people. In the next line, there are n integers indicating the ages. Input is terminated with a case where n = 0. This case should not be processed.
しゅつりょく
For each case, print a line with n space separated integers. These integers are the ages of that country sorted in ascending order. Warning: Input Data is pretty big (∼ 25 MB) so use faster IO.
入力サンプル
5 3 4 2 1 5 5 2 3 2 3 1 0
出力サンプル
1 2 3 4 5 1 2 2 3 3
問題を解く構想.
データ量は非常に大きいが,数値範囲は小さいことに気づいた.
参照コード1(210 ms)

#include
#include
int age[101];
int main(){
	int n;
	while(scanf("%d",&n) && n){
		memset(age,0,sizeof(age));
		int old;
		for(int i=0;i<n;i++){
			scanf("%d",&old);
			age[old]++;
		}
		int first=0;//         
		int i=1; 
		while(i<=100){
			if(age[i]>0){
				if(first!=0) printf(" ");
				printf("%d",i);
				age[i]--;
				first=1;
				continue;
			}
			i++;
		}
		printf("
");
	}
	return 0;
}

リファレンスコード2(50 ms)

#include
#include
#include

inline int readint(){
	char c=getchar();
	while(!isdigit(c)) c=getchar();
	
	int x=0;
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}

int buf[10];
inline void writeint(int i){
	int p=0;
	while(i){
		buf[p++]=i%10;
		i/=10;
	}
	for(int j=p-1;j>=0;j--){
		putchar('0'+buf[j]);
	}
}

int main(){
	int n,x,age[101];
	while(n=readint()){
		memset(age,0,sizeof(age));
		for(int i=0;i<n;i++){
			age[readint()]++;
		}
		int first=0;
		int i=1;
		while(i<=100){
			if(age[i]>0){
				if(first) putchar(' ');
				writeint(i);
				age[i]--;
				first=1;
				continue;
			}
			i++;
		}
		putchar('
');
	}
	return 0;
}