By Sad_reacts_only, history, 5 weeks ago,

I have made a submission to problem — 1398G - Соревнования по бегу 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?

• +10

 » 5 weeks ago, # | ← Rev. 2 →   0 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.
•  » » 5 weeks ago, # ^ |   0 Actually the pragmas are commented, with pragmas it just makes very less Change
•  » » » 5 weeks ago, # ^ |   0 Oh I didn't really see that and submitted exactly the same code and got TLE 90029372.
 » 5 weeks ago, # |   +7 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?
•  » » 5 weeks ago, # ^ |   0 In general in Codeforces c++17 is slower than c++14 that's why i prefer c++14
•  » » » 5 weeks ago, # ^ |   0 The 64-bit version is faster than all: 90049519
•  » » » » 5 weeks ago, # ^ |   0 probably because it becomes $n^2/64$ instead of $n^2/32$
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +15 No. This blog says it's still 32.
•  » » » » » » 5 weeks ago, # ^ |   0 oh interesting