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

Автор IloveGoodness, история, 3 года назад, По-английски

Printing ":-)" $$$10^6$$$ times takes about 2.6s in CF (131141089) while it takes just 0.7s in my machine (with 2.4 GHz cpu). I found this issue after tying to solve a problem which required $$$10^6$$$ output lines. My initial blog:

Please take a look at: 4021643 and 6576225. They are exactly same but one runs in 2s the other in 0.1s. Accepted solution was sent 10 month later. Again I submitted same solution after 8 years and got TLE 130976507 while in my computer, runs in just 0.188s

There is a bug in CF compiler for sure, Please solve this issue Mikemizayanov.

Thanks :)

UPDATE: I submitted printing $$$10^6$$$ times program on AtCoder (Link). Here is the result:

Codeforces: 2.6s VS Atcoder: 0.066s

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by IloveGoodness (previous revision, new revision, compare).

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

You do not initialize ans variable. It seems, that you were just lucky enough to pass all the tests with the solution; however, it must be undefined behaviour.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by IloveGoodness (previous revision, new revision, compare).

»
3 года назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

That's the best you can get for free, use PaidPascal for better results

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Pascal is far from the only language on Codeforces in which the "default" I/O methods are slow and fast I/O is possible with a bit more effort. Starting with no Pascal knowledge, a few minutes of searching documentation led me to writing the following program, which also prints a million lines of ": )", but does so quickly.

code
  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Wow! I didn't know about this. Unfortunately we can't use your code on problems which need different output lines Like this also default pascal I/O is actually fast enough that I haven't seen anybody using alternative methods.

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

      It seems to me that you can just overwrite the contents of the array between calls to BlockWrite to output whatever you want to. Of course, writing numeric data in this way is inconvenient, since there may not be built-in tools to perform the encoding for you in this case. It may surprise you to learn that some people write and use small custom libraries to do this even in C++, where the advantage of doing so is much smaller.

      EDIT: You are of course free to investigate on your own the reasons writeln is no longer as fast on Codeforces as 4021643 demonstrates it once was. But in the meantime I hope you now have the tools to work around it whenever you need to.

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Thanks a lot:) Your solution is really good. But still CF needs to be faster because Atcoder executes same program in just 0.066s.