Can anyone give me the main idea to solve APIO 2012 Problem 2 Guard?

It is clear that when a guard reported 1 in a range A, then some guards reported 0 in every position in range A except position I. we are certain that there is a ninja at position I. After calculating all positions that way(let's say we have found IS such positions), we still have K-IS ningas and that information can help us be certain about other positions, but I didn't know how to solve this problem in less than O(n²).