In working on upsolving https://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://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://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!
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.
Ah yeah idk why I didn't think of duplicates, thank you!
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.