amanmehta-maniac's blog

A code with a 10^15 loop gets accepted in 15ms.

By amanmehta-maniac, history, 7 years ago, In English

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://codeforces.com/problemset/problem/371/C

Solution link: http://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. :)

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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 -O2 or -O3 to 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.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, that is smart! Thanks Jakube! :)

→ Reply