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

Strange complier behaviour in round 978 (Div. 2) E1
Автор Harsh_kunwar, история, 7 недель назад, По-английски

In the recent Div2 contest Codeforces Round 978 (Div. 2), I attempted solving E1 2022E1 - Billetes MX (простая версия). Upon submitting, the judge returned a TLE on pretest 30 285739225. This result was unexpected since my solution had a time complexity of O(n*30). After the contest ended, I revisited my code and made a small change by replacing push_back with emplace_back. I then resubmitted the code, and surprisingly, this time it was accepted 285743685. I am unsure why this happened—whether the time limit was too strict or if this was not the intended solution. Can someone please address my issue ?

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

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

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

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

push_back copies and emplace_back moves; that's the main difference.

But had you used emplace_back({c, val}); or emplace_back(make_pair(c, val)); it calls the copy constructor, which is as costly as a simple push_back unlike emplace_back(c, val) which doesn't construct a pair here but calls the constructor of pair directly reducing a copy operation.

More detailed info can be found here.

→ Ответить