Блог пользователя Elhabashy

time complexity
Автор Elhabashy, история, 5 лет назад, По-английски

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

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

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.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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).

→ Ответить