haochenkang's blog

TLE from unordered_set C++
By haochenkang, history, 3 years ago, In English

Hello Codeforces community!

I have a question regarding question B in the recent CodeTon round.

My solution passed all pretests, but TLE on test 22 in the main tests. My code is: 150736681

I used an unordered_set to keep tracking of the seen elements. However, when I changed it to set, the solution passed main tests too. I have always thought that unordered_set is faster than set. Can someone please explain to me what's happening here?

Thanks for any help!

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

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

Read Blowing up unordered_map

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi codemastercpp,

    Thanks for your prompt reply!

    Should I always use set instead of unordered_set? How should I decide which one to use?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if complexity allows, I prefer using set/map over unordered_set/unordered_map however, if constraints are tight, I use safe_map that is described in the blog I mentioned.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/blog/entry/68000

→ Reply