I was recently wondering what complexity loop can be used in less than 1 sec. For the same, I took one of my previously solved problems and added an extra loop but, even after I increase the looping to as high as 10^15, I get Accepted within 15ms. How could this happen?
Problem link: http://mirror.codeforces.com/problemset/problem/371/C
Solution link: http://mirror.codeforces.com/contest/371/submission/27344927
PS: If this a bad place to ask for this query, please let me know where to post this. :)
The compiler is able to figure out, that this code doesn't do anything (cc is never used). And so he is able to completely remove the for loop.
Notice, this will only happen, if you enable the optimizer. If you don't pass
-O2or-O3to the compiler, it will actually compile the loop and the program will take quite a long time to finish. You can see the different generated assembler with and without optimizer here.That's great, never knew about this. Thanks, @jakube.
Wow, that is smart! Thanks Jakube! :)