WA TC74?! Help on Problem 558D, "Guess Your Way Out! II"

Revision en2, by ekzhang, 2015-07-21 04:25:29

Hi, could someone help me on this problem? I keep getting WA on test case 74, and I can't figure out why. This is my latest submission without debugging code.

My code works like this: I first turn all the replies into [L, R] ranges on the bottom row. Then I take all the "yes" replies, and use all of them to get an initial, single [lo, hi] bound on the exit node. I sort the "no" replies in ascending order of L, then iterate through them, while updating lo. If at any time, lo > hi, we can end the loop.

For each of the "no" replies, check if there's any gap between lo and L. If there is, those gaps are all possible exits, and deal with them like that. Regardless, set lo to be max(lo, R + 1) at the end of every loop, as we've handled all possible nodes  ≤ R.

At the end of the program, do some casework, and output different answers based on that.

The program works for the first 73 cases, but it outputs "Data not sufficient!" for test case 74, which is incorrect. Help finding the bug would be greatly appreciated!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ekzhang 2015-07-21 04:25:29 8
en1 English ekzhang 2015-07-21 04:17:01 1147 Initial revision (published)