Wavator's blog

What happened?

By Wavator, history, 6 years ago, In English 
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.

  • Vote: I like it
  • +21
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it +37 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +14 Vote: I do not like it

    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

    → Reply