Sad_reacts_only's blog

By Sad_reacts_only, history, 7 weeks ago, In English

I have made a submission to problem — 1398G - Running Competition My submission — 90009972

According to me, it's time complexity is O(n^2 / 32) and n is 2*10^5. Then why it's not TLE? or am I calculating the time complexity wrong?

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

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

The code you wrote is in fact $$$O(\frac{n^{2}}{32})$$$ but apparently the operations that are being made are simple enough for compiler to somehow optimise them. I've tried to submit the same code without pragmas and it got TLE so yeah, it's a matter of compiler optimisation. Similar thing happend in the very same contest, some people submitted brute force solution in $$$O(n^{2})$$$ $$$n \leq 10^5$$$ for problem C and got accepted despite many hacking attempts.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually the pragmas are commented, with pragmas it just makes very less Change

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh I didn't really see that and submitted exactly the same code and got TLE 90029372.

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

I don't understand the code but I'm going to point out a very strange behaviour.

Siata used C++17 to run the code. Sad_reacts_only used C++14 to run the code. I was a bit curious so I ran the code several times and observed that C++11 and C++17 gave TLE every time but C++14 gives AC every single time. Isn't this strange considering that C++17 is supposed to be faster than C++14?