GCJ 2020: Blindfolded Bullseye

BlindfoldedBullseye.kt

fun main() {
    val t = readLine()!!.split(" ")[0].toInt()
    val s = 1_000_000_000
    val n = 9
    val d = (2 * s) / (n + 1)
    fun hit(i: Int): Int = -s + i * d
    fun ask(x: Int, y: Int, swap: Boolean = false): Boolean? {
        println(if (swap) "$y $x" else "$x $y")
        return when (readLine()!!) {
            "CENTER" -> null
            "HIT" -> true
            "MISS" -> false
            else -> error("cannot")
        }
    }
    fun bisect(l0: Int, r0: Int, y: Int, right: Boolean, swap: Boolean): Int? {
        var l = l0
        var r = r0
        while (l < r - 1) {
            val m = (l + r) / 2
            val aa = ask(m, y, swap) ?: return null
            if (aa xor right) {
                r = m
            } else {
                l = m
            }
        }
        return if (right) return l else r
    }
    fun find(x: Int, y: Int, swap: Boolean): Int? {
        val xl = bisect(-s - 1, x, y, false, swap) ?: return null
        val xr = bisect(x, s + 1, y, true, swap) ?: return null
        return (xl + xr) / 2
    }
    fun check(x: Int, y: Int): Boolean {
        val a = ask(x, y) ?: return true
        if (!a) return false
        val x0 = find(x, y, false) ?: return true
        val y0 = find(y, x, true) ?: return true
        check(ask(x0, y0) == null)
        return true
    }
    cases@for (case in 1..t) {
        for (i in 1..n) {
            for (j in 1..n) {
                if (check(hit(i), hit(j))) continue@cases
            }
        }
    }
}