First I used binary search, 0.271s, that's a bit slow.
So I used hash, 0.156s, still not fast enough.
I guess the biggest problem is that input is not very quick, then I decided to make a special "scanf" which reads chars one by one and translate them into int.
It's very useful, it worked in 0.078s.
After that, I optimized other staff. It's 0.062s.
And... With a little luck... I've got 0.049s once, with the same code.

In a word, my HINT for you to get 0.078s is:
USE HASHTABLE AND YOUR OWN INPUT FUNCTION!

Forgive me if my English is not very good. Hope these can help you guys somehow. Good luck.

You can get it even better:)
Some perversion involved, though.

Yeah, I saw your submissions this morning, 0.031s. Orz

Edited by author 03.10.2009 14:54

Though, I still don't like that sometimes the same code can get different running time.

Yeah, my 0.046s is absolutely by chance. I just came up with a new idea to make it quicker, I'll try it out...
But how do some people get 0.001s at some problem? I even can't get it at 1000!

Edited by author 04.10.2009 19:35