Harsh_kunwar's blog

Strange complier behaviour in round 978 (Div. 2) E1
By Harsh_kunwar, history, 6 weeks ago, In English

In the recent Div2 contest Codeforces Round 978 (Div. 2), I attempted solving E1 2022E1 - Billetes MX (Easy Version). 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 ?

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply