→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 17.04.2026 08:18:03 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
The hashing is not perfect and with specific test cases, every find, insert etc. works in O(n) instead of O(1). Refer to this for more detail.
But here all keys are ints and not int64_t/long longs, so their hashes do not (should not?) collide, so what's the real reason?
https://mirror.codeforces.com/blog/entry/62393 this might help??
If you look at the TLE testcase, it's pretty obvious what's going on: The input consists of exactly the multiples of 53201. They have different hashes, but these hashes all get mapped into the same bucket when the unordered map reaches the right size. Only the latter is needed for the bad worst-case performance of unordered_map to occur.
yes, thank you, we figured this out in another thread too, I forgot about the % bucket_count part
so should we avoid using unordered_map in contests and stick to map or use some custom hash with unordered_map like this.
Using unordered_map with default hash on Codeforces is just begging to get hacked or fail system tests. What you do instead is up to you. Options include:
Ordering | increasing order | no ordering | (by default) |
Implementation | Self balancing BST | Hash Table | like Red-Black Tree |
search time | log(n) | O(1) -> Average | | O(n) -> Worst Case
Insertion time | log(n) + Rebalance | Same as search
Deletion time | log(n) + Rebalance | Same as search
so the answer of your problem is in worse case unordered_map uses O(n) for each insertion .So your insertion in the testcase no 12 will take upto O(n^2) in your unordered map ,but it will take only O(nlog(n)) in map.
https://www.geeksforgeeks.org/map-vs-unordered_map-c/ link for reference