ekzhang's blog

By ekzhang, history, 6 years ago, In English

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!

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

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

Can someone tell me why this post was downvoted?

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

The line " if ( L — lo > 1 || ans != -1) " doesn't take into account the case where L > hi. Try this case, for example:

4 2
4 8 8 1
4 12 12 0

Here's your code modified to pass: 12140485