masterchief164's blog

Same code gives different answers on different platforms.
By masterchief164, history, 3 years ago, In English

1399C - Boats Competition
I've tried to solve the problem using both maps and unordered_maps The failed code and the accepted code.
The accepted code used maps and the failed code uses unordered_maps. But the funny thing is that when I run the code on my machine it gives the correct output while when I submit the code it fails. I know that maps sorts it's elements while unordered_maps don't. Moreover there is no need of sorting the elements as per the question as it requires simple brute force.
I've tried to run it on gcc 17 on my machine (hope it helps). Here is the output on my machine.

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

Comments Comments (5)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

CLICK 1
CLICK 2

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Neither of the links help in my case. What do u think that I'll directly post a problem blog without googling anything?

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

The problem is that the key s - x.first might not exist in the map but you are inserting it by maps[s - x.first] > 0 in the 115th line. So at this point, if a rehash happens the order of everything in the map changes and this might cause x to miss some elements of the map. Here is a link to the accepted code with unordered_map (added maps.find(s - x.first) != maps.end() to the 115th line).

UPD: Sorry my bad. In case of a rehash, all iterators are invalidated and this causes undefined behavior. you can read more here.

→ Reply