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

MY AC Solution 0.203 (Be careful, spoilers!)
Posted by KOTMAKRUS 6 Apr 2014 16:16
Create an array of Boolean elements. Size = billion.
For i:=1 to n {{ introduce a variable; element of array with index [variable] equals true }}
For i:=1 to m {{ introduce a variable; if element of array with index [variable] equals true then increase the counter }}

And finally, we output counter))
That's all), sorry for bad english

But this solution takes 58 mb of memory... ((

Edited by author 06.04.2014 16:17
Re: MY AC Solution 0.203 (Be careful, spoilers!)
Posted by BillSu 25 Apr 2014 14:15
Then, your code is just using a hash table method.
But I check the solution rating, someone can do it in 0.015, and many persons do it below 0.1.
How can they do that? Is because that compiler different?
Re: MY AC Solution 0.203 (Be careful, spoilers!)
Posted by Kello-Kustaa Kuolema 27 Oct 2017 01:58
BillSu wrote 25 April 2014 14:15
Then, your code is just using a hash table method.
But I check the solution rating, someone can do it in 0.015, and many persons do it below 0.1.
How can they do that? Is because that compiler different?

It's not that hard to do it under 0.1 with C. Decent hash implementation and optimized input reading (scanf is too slow!) will actually do the 0.031 trick. 0.062 is achievable with a binary search. I achieved 0.015  by optimizing things speedwise a bit more and using as much memory as was allowed.

(studied just for fun a bit how slightly different schemes perform, have to try a few more ideas later, my current 0.015 solution is far from the optimum.)