?
# | 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 |
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)) }
?
?
?
?