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

Getting TLE on test 45 using same logic as mentioned in editorial.
Автор AnestheticCoder, история, 2 года назад, По-английски

Hello everyone, I was solving problem C of a div 3 contest 1702C - Поезд и запросы and I just used 2 hash maps to stores the first and last occurence of each station, but on test case 45 its saying TLE.

165981690

Then i read the editorial and tried to using just one hashmap but still it says TLE.

165982877

Please Help.

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

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

Only replace unordered_map with map

map: 165985542

unordered map: 165981690

and after adding fast I/O it will work in 576 ms instead of 2043 ms.

Fast I/O code: 165987488

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

May be due to slow I/O. Please try to add ios_base::sync_with_stdio(false); cin.tie(nullptr); at the beginning.

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

worst case complexity of searching, insertion, deletion in std::unordered_map is $$$O(n)$$$

- How to save yourself from getting hacked?

After some searching around we run into unordered_map.h. Inside the file $$$...$$$

$$$...$$$ Armed with this knowledge, we can insert lots of multiples of one of these primes to the map in order to get $$$n^2$$$ blow-up

You can read the full thing here.

- Over 350 hacks by beethoven97 on this one problem

You can see many people got hacked in that contest due to this same issue.

→ Ответить