ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1196. History Exam

AC 0.046s! HINT for you to get 0.078
Posted by tiancaihb 30 Aug 2009 19:53
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.
Re: AC 0.046s! HINT for you to get 0.078
Posted by gvsmirnov 3 Oct 2009 06:57
You can get it even better:)
Some perversion involved, though.
Re: AC 0.046s! HINT for you to get 0.078
Posted by tiancaihb 3 Oct 2009 14:53
Yeah, I saw your submissions this morning, 0.031s. Orz

Edited by author 03.10.2009 14:54
Re: AC 0.046s! HINT for you to get 0.078
Posted by gvsmirnov 4 Oct 2009 04:52
Though, I still don't like that sometimes the same code can get different running time.
Re: AC 0.046s! HINT for you to get 0.078
Posted by tiancaihb 4 Oct 2009 19:29
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