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

What happened?

Автор Wavator, история, 6 лет назад, По-английски 
Last educational round I solved problem C with same code but different version of c++.

In GNU C++ 11 I always get AC, the time cost is about 1800 ms 39144604 , 39119187 , but in c++14 I can't pass test 28(TLE). 39144564. Codes of the 3 submissions are exactly same. It confuses me.

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

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

Note that not only c++ standard versions differ but also compiler version. It is not surprising for performance to slightly vary between compiler versions. While compiler makers try to not make things worse it is not too uncommon having changes that improve performance of some programs and decrease for others. In your case the accepted solution is within 10% of time limit. So even small changes in performance could cause it to TL. Seeing that other accepted solutions are far from TL 50-400ms your solution probably has some mistake. You can probably improve something to make it AC more reliably. The TL test case starts with a lot of ))))))))), your solution in such case inserts symbols at the start of string one by one making it O(n2) . n2 solutions with n ≤ 105 are usually not supposed to pass, but with large time limits, fast computer and some luck it might barely pass.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

    It is not a ON*N solution as far as I am concerned. The statement of the problem shows that the sum of the length is less than or eq to 300000, so at the worst case, I only need to add 300000 (or). The string operation + is too slow, if I really want to use this algorithm and pass all versions, I need to write is as puah_back several times and do one operation of add. ON solution I have writtern and submitted. And, thank you!

    upd: it is ON*N, sorry

    → Ответить