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

unordered_map VS map
Автор Adibov, история, 6 лет назад, По-английски

What's wrong with unordered_map? Shouldn't be faster than map? I just submitted two solution with map and unordered_map and first one got TLE while second one got ACC. Could you please say why?

TLE: 48262291

ACC: 48262284

Even i reserved it: 48262508

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

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

This might help :) The search time for an unordered map is of O(n) in the worst case.

→ Ответить
»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

You can use gp_hash_table. I modified your solution and got AC in 2700ms.

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

    Appreciate that.

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

    I think that using gp_hash_table in the competition may also be hacked by others, especially div.3 or Educational Codeforces Round. In my opinion, when we solve the problem, if the time complexity of the prediction is sufficient, it is better to use a more stable algorithm.

    In fact, I have the same experience as you. I was also hacked when I solved this problem, and then I realized the problem caused by using hash. QAQ

    Blowing up unordered_map, and how to stop getting hacked on it

    → Ответить