Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

 
 
 
 
General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
86603930 Practice:
655editorial
1372F - 36 Kotlin 1.4 Accepted 1419 ms 39916 KB 2020-07-11 23:51:17 2020-07-11 23:51:17
→ Source
import kotlin.math.max
import kotlin.math.min

fun main() {
    val n = readLine()!!.toInt()
    val answer = IntArray(n + 1)
    val occurrences = mutableMapOf<Int, MutableList<Int>>()
    fun query(l: Int, r: Int): Pair<Int, Int> {
        println("? $l $r")
        val line = readLine()!!.split(" ")
        return Pair(line[0].toInt(), line[1].toInt())
    }
    fun calc(l: Int, r: Int, ePrev: Int) {
        if (l > r) {
            return
        }
        var q = query(l, r)
        val x = q.first
        val f = q.second
        var e = ePrev
        while (1 shl e > f) {
            e--
        }
        if (e < ePrev) {
            var j = l - (l % (1 shl e))
            if (j < l) {
                j += 1 shl e
            }
            while (j <= r) {
                if (j % (1 shl ePrev) != 0) {
                    q = query(j, j)
                    occurrences.computeIfAbsent(q.first) { mutableListOf() }.add(j)
                }
                j += 1 shl e
            }
        }
        val ixs = occurrences[x]!!
        var leftBound = 0
        if (ixs.size == 1) {
            q = query(max(l, ixs[0] - (1 shl e) + 1), ixs[0])
            if (q.first == x) {
                leftBound = ixs[0] - q.second + 1
            } else {
                q = query(ixs[0], min(r, ixs[0] + (1 shl e) - 1))
                leftBound = ixs[0] + q.second - f
            }
        } else {
            q = query(max(l, ixs.min()!! - (1 shl e) + 1), ixs.max()!!)
            leftBound = ixs.max()!! - q.second + 1
        }
        for (j in leftBound until leftBound + f) {
            answer[j] = x
        }
        calc(l, leftBound - 1, e)
        calc(leftBound + f, r, e)
    }
    calc(1, n, 20)
    println('!' + answer.joinToString(" ").substring(1))
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details