Dramatic Difference between Unordered Set and Policy Based Hash Table

Revision en1, by harryzhengipsum, 2022-11-16 01:01:44

On 704A - Thor, the policy-based hash table easily passes under the time limit, but the unordered set version TLEs on case 56.

With gp_hash_table: 181117819

With unordered_set: 181133673

Both submissions use a custom hash function, so it can't be due to collisions. On test case 56, the unordered_set suddenly gets TLE but it's only slightly slower than the gp_hash_table on all the other test cases. Why is this?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English harryzhengipsum 2022-11-16 01:01:44 522 Initial revision (published)