the_stone_dawg's blog

Difference between using a map to iterate in sorted order vs. manually sorting an array
By the_stone_dawg, history, 4 years ago, In English

In working on upsolving https://mirror.codeforces.com/contest/1513/problem/D, I ran into this weird aspect of c++ I need some help explaining:

Part of the solution involved iterating over a sorted ordering, which I initially achieved by inserting everything into a map (not hashmap). I understand that iteration over a map in c++ should produce elements in sorted order. However, this produced a WA result, like in this submission: https://mirror.codeforces.com/contest/1513/submission/112967965.

On replacing the map with an array and then manually sorting that array however, the solution was accepted, like here:https://mirror.codeforces.com/contest/1513/submission/112968002

The only difference between the two submissions is changing the map to a sorted array. To me the logic seems equivalent; iterating over a map should produce an equivalent sorted ordering to the one if you manually sorted an array, however it seems like thats not the case. I was wondering if anyone had any insight on why?

Thanks!

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

»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

One difference is that duplicate v[i] keys will only cause one {v[i],i} pair to remain in a map, while the vector will store all {v[i],i} pairs. Maybe using a multimap might be more fitting here.

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I am pretty certain a map does not support duplicated copies of an "index". so if in your array you had any two v[i]'s equal it would fail.

i ran the following test case:

1

5 10

2 3 4 2 2

on your codes in custom invoc and your map code produced 40 while your ac code produced 24 (which is correct). i replaced your map with multimap (and no other changes) and it works for my test case (it actually ac's as well) so the thing here is to use a multimap instead of a normal map. or better just use regular sorting everytime.

→ Reply