NM_Mehedy's blog

By NM_Mehedy, history, 3 years ago, In English

To solve this problem, I used biteset. The size of the bitset should be at least $$$10^4$$$. I used $$$10$$$ so that it's easy to debug. At the end I forgot that the size of bitest should be changed and submitted this code.The Verdict should be Wrong Answer/ Run time error. But it got Accepted.

Does anyone know the reason behind this?

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

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

You can check that it works for bitset size <= 32 and gets runtime error for anything bigger. That's because libstdc++'s bitset has a specialized case for size <= 32 when it uses a single long value to store all data and then it doesn't need to calculate offsets. All memory accesses use only those 4 bytes, so you don't get runtime error.

Of course accessing bitset at positions bigger than its size is undefined behavior, so it's hard to predict what this code is actually doing. You can be sure that it's not the correct solution and it got accepted because of weak tests.

A probable explanation is that all bitset accesses are performed modulo 32. Doing this explicitly gets AC (120690657), so these tests don't catch that.