Submission #1545977

---

Source Code Expand

fun main(args: Array<String>) {
    val a = readLine()!!.map { it == '1' }.toBooleanArray()
    val b = readLine()!!.map { it == '1' }.toBooleanArray()
    fun f(i: Int) = (i + a.size) % a.size
    if (b.all { !it }) {
        println(-1)
        return
    }
    val left = IntArray(a.size)
    val right = IntArray(a.size)
    var t = b.lastIndexOf(true)
    for (i in left.indices) {
        left[i] = if (b[i]) 0 else t + 1
        t = left[i]
    }
    t = b.indexOf(true)
    for (i in right.indices.reversed()) {
        right[i] = if (b[i]) 0 else t + 1
        t = right[i]
    }
    var res = a.size * 5
    for (sh in -a.size..a.size) {
        val flip = a.indices
                .filter { a[it] != b[f(it + sh)] }
                .map {
                    Pair(
                        Math.min(left[it], Math.max(left[it] + sh, 0)),
                        Math.min(right[it], Math.max(right[it] - sh, 0))
                    )
                }
                .toTypedArray()
                .sortedBy { -it.first }
        var shifts = 0
        if (!flip.isEmpty()) {
            shifts = flip[0].first
            var tRight = flip[0].second
            for ((pLeft, pRight) in flip.drop(1)) {
                shifts = Math.min(shifts, tRight + pLeft)
                tRight = Math.max(tRight, pRight)
            }
        }
        res = Math.min(res, shifts + flip.size + Math.abs(sh))
    }
    println(res)
}

Submission Info

Judge Result