Discussion @ 1209. 1, 10, 100, 1000... @ Timus Online Judge

Strange - not so simple if u use sqrt - TL(+)

Posted by Hristo Stefanov 26 Aug 2005 19:11

My solution using sqrt (in C++ using cin and cout) failed because ot TL - it's the same solution that they suggest bellow!!!
O( N * sqrt(2^31))
Then i did it with binary search :
O( N * log2(2^31) AC in 0.5secs
Just curious what are the AC times for the sqrt method.

Re: Strange - not so simple if u use sqrt - TL(+)

Posted by Madhav 14 Jun 2008 13:34

mine got accepted in 0.109sec using sqrt() func.

Edited by author 14.06.2008 13:35

Re: Strange - not so simple if u use sqrt - TL(+)

Posted by Pavel Otchertsov 13 Nov 2008 00:41

i've got AC in 0.078.
I used the binary_search and array with positions of "1"

Re: Strange - not so simple if u use sqrt - TL(+)

Posted by a_dergachev 14 Mar 2009 19:33

0.031 seconds, using one sqrt per line of input

Discussion of Problem 1209. 1, 10, 100, 1000...