For a great while of my CP career I had no idea how such, at a first glance, insignificant things might affect the runtime of the code. And till this day I keep seeing many beginners having lack of knowledge about this so-called effect, that's why I would like to share it here and hope it'll help you out someday.
1 code 164992399 executes in a time of 1918ms.
2 code 164991769 executes in a time of 280ms.
Notice 2 drastically different runtimes (6x difference!). The reason for that is pretty straightforward: in this code one of three IF statements (IF statement with == 2) gets a true response way more often than others. While the first code has an IF statement with 2 at the end, the second code has such IF statement at the beginning.
Knowing this we can make a conclusion: the order of IF statements matters, and sometimes matters a lot (you get AC or TLE). So whenever you hit (or feel you might hit) the bound of the time limit you always want to check whether all IF statements are placed in the right order and if not — a little change might make you happier by seeing this lovely green Accepted word.
upd. As Apachee mentioned in the comments if you wish to avoid thinking where it is better to put one or another IF statement you can use switch-case method which helps to achieve the same runtime as the second code 165019894.
Using switch statements in such cases might help you negate the effect of different rearrangements, because I believe switch statements translate to calculating the address to jump to, and then jumping there. For example, if you write switch statement with 3 cases: 1, 2, and 3, then it might result in something like
I don't know exactly how switch statements are translated into assembly, but that's what I believe after looking at a few different programs in disassemblers.
Also you might want to look at
[[likely]]
and[[unlikely]]
attributes, which are available in C++20.Appreciate your help!
I thought that if statements and switch-case are identical and have same speed, but you provided me with new knowledge that switch case can help in case of rearrangements and enhances speed instead of equivalent if else
More about how switch statements might be optimized
This blog is an absolute gem. Very useful, thanks.
You use
MX = 1e3+1
in one butMX = 1e3+2
in the other. I changed the constant back and got 717 ms. 165025789Oh indeed, this code was submitted long time ago so I'm not sure if I remember what happened there.
upd. I resubmitted both codes and they both still stay in the same bracket (280-330), however some differences occure because of CF system I believe. So seems it's not the thing in this code.
So, the conclusion from the blog is incorrect right? Why don't you update the blog then?
I explicitly mention that fft's point doesn't change anything, read the "upd." section again.
ok thnx