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?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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?
Name |
---|
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.
Actually the pragmas are commented, with pragmas it just makes very less Change
Oh I didn't really see that and submitted exactly the same code and got TLE 90029372.
I don't understand the code but I'm going to point out a very strange behaviour.
Zadymiarz12345 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?
In general in Codeforces c++17 is slower than c++14 that's why i prefer c++14
The 64-bit version is faster than all: 90049519
probably because it becomes $$$n^2/64$$$ instead of $$$n^2/32$$$
No. This blog says it's still 32.
oh interesting