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

Автор NM_Mehedy, история, 3 года назад, По-английски

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?

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

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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.