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

Автор tenshi_kanade, история, 9 лет назад, По-английски

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?

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

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

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

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

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