Adibov's blog

unordered_map VS map
By Adibov, history, 6 years ago, In English

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

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

»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Appreciate that.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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

    → Reply