PKU1002(3)

前回のコードの問題を解決しましょう。
ここに現段階(3/28 00:15)の最短コードがあるのでネタばれ注意

まず、mapが遅い。
logNのオーダーなので普段ならたいして問題ないのですけど、
きっと凄い量のテストが来るのでしょう。
次にiostreamも遅い。
C++ は諦めてCで書けっちゅうことなのかな？

まず、最初にmapは値域が限定されてるので配列で代用できます。
が、ここで罠があります。

最初は素直に int[10000000]にしたのですがMLEでアウトになりました。
なのでメモリを節約するためにunsigned short[10000000]にしましたが、
こんどはWrong Answerで通りません。
おそらく65536個以上重複するテストがあると思われます。

これを解決する方法はただ一つ。
3byteの整数型を使えばいいのです。
と言ってもそんな型はないので自力で演算しましょう。

m['rqA'],d,i,q=m,*r;
char*p;
main(c,s){
	for(;gets(p=s);d=i--?!++*(r=q+d*3):0)
		for(;c=*p++;)
			c-45?d=d*10+(c-48<10u?c-48:(c-c/82-59)/3):0;
	for(;c<10000000;++c)
		(i=*(r=q+c*3)<<8>>8)>1?
			d=printf("%03d-%04d %d\n",c/10000,c%10000,i):0;
	d||puts("No duplicates.");
}

なおリトルエンディアンに依存したコードなのでビッグエンディアンでは動きません。