tenshi_kanade's blog

By tenshi_kanade, history, 9 years ago, In English

I've recently come across a very strange problem using C++ 11.

I submitted a solution for problem 620C - Pearls in a Row using unordered_map and got TLE, then I submitted the exact same solution using map (it's supposed to be slower: O(1) amortized VS O(logN) per operation) and it got Accepted with 280 ms.

Submission with unordered_map: 15756653

Submission with map: 15759645

Is this some kind of problem with the C++11 compiler used here on Codeforces? Anyone got a clue?

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Looking at the different execution times, for both submissions, unordered_map seems to be faster, maybe that particular case is antihashing and a lot of collisions happen? That could explain the TLE