hello everyone , why my submission in this problem accepted ? the time complexity of code in worst case is (10 ^ 12 ) , There are 17 attempts to hack my code but all are falid
the problem : 1238A - Prime Subtraction
my submission : 62130511
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
hello everyone , why my submission in this problem accepted ? the time complexity of code in worst case is (10 ^ 12 ) , There are 17 attempts to hack my code but all are falid
the problem : 1238A - Prime Subtraction
my submission : 62130511
Name |
---|
GNU C++ compiler is very smart :)
When it tried to compile your code, it saw:
1) if n<3, answer is NO.
2) if n>=3, then:
a) if n changed, answer is YES
b) if n hadn't changed, answer is YES too
So, in executable file your function "factorize" is never used.
How to see it?
At first, if you will write cout<<n<<endl in "factorize" function, your solution will immediately get TL.
At second, there is a site https://godbolt.org which shows you how your code looks like when it is already compiled.
Yep, it is very smart! Sometimes I cannot optimize my code in a complex code(that doesn't access arrays and doesn't do heavy operations). I leave it for the compiler to do its final job! ;)
thank you for explain this Wind_Eagle
I am not sure but I feel this is due to O2 optimization. I have tried your code on my local compiler and easily found a testcase that times it out. Codeforces uses very optimizing flags for best performance especially unroll loops which I feel is the reason for your fast code execution. You are not accessing any array which even fastens the code. All you are doing is simple operations and not heavy ones(except for the modulo in while loop which you don't check on a lot).
If I'm not mistaken this happens without -O2 too.
I guess. But somehow, it doesn't work with my local compiler. I have C++11 default flags on. I am not sure why it doesn't work. If you have a method to enable such on my local compiler, can you tell me it?
thank you for help
Ahmadsm2005
You're welcome!