/** * Fist scan all columns current lowest point if we need to investigate them. * Then binary search, with some smart boundary management. * * this might need ~20k queries in the worst case I can think of. * * Based on Arrays#binarysearch(). * Reminds me of the article of programming pearls, Column 4 writing correct programs. * Implementing binary search remains error-prone. */ fun main() { val input = System.`in`.bufferedReader() val output = System.out.bufferedWriter() val (maxX, maxY) = input.readLine().split(" ", limit = 2).map { it.toLong() } var bestX = 0L var bestY = 0L var currentX = 1L var low = 1L var high = maxY val stack = mutableListOf() while (currentX <= maxX) { // First try to see if an improvement can be found here output.write("? $currentX $low\n") output.flush() if (input.readLine() == "building") { bestY = low low = (low + 1).coerceAtMost(maxY) stack.add(currentX) } currentX++ } bestX = stack.last() while (stack.isNotEmpty()) { currentX = stack.removeLast() // now we binary search since we can find an improvement while (high >= low) { val mid = ((low + high) / 2).coerceAtMost(maxY) output.write("? $currentX $mid\n") output.flush() when (input.readLine()) { "sky" -> { high = mid - 1 if (high < low && mid - 1 > bestY) { bestY = mid - 1 bestX = currentX } } "building" -> { low = mid + 1 if (high < low && mid > bestY) { bestY = mid bestX = currentX } } } } low = bestY + 1 high = maxY } output.write("! $bestX $bestY\n") output.flush() }