提出 #53893982

---

ソースコード 拡げる

import java.io.*
import java.util.*
import kotlin.collections.*
import kotlin.math.min

val INPUT: InputStream = System.`in`
val OUTPUT: PrintStream = System.out

val _reader = INPUT.bufferedReader()

var _tokenizer: StringTokenizer = StringTokenizer("")
fun read(): String {
    while (!_tokenizer.hasMoreTokens()) {
        _tokenizer = StringTokenizer(_reader.readLine() ?: return "", " ")
    }
    return _tokenizer.nextToken()
}

fun readInt() = read().toInt()
fun readDouble() = read().toDouble()
fun readLong() = read().toLong()
fun readStrings(n: Int) = List(n) { read() }
fun readInts(n: Int) = List(n) { readInt() }
fun readIntArray(n: Int) = IntArray(n) { readInt() }
fun readDoubles(n: Int) = List(n) { readDouble() }
fun readDoubleArray(n: Int) = DoubleArray(n) { readDouble() }
fun readLongs(n: Int) = List(n) { readLong() }
fun readLongArray(n: Int) = LongArray(n) { readLong() }

val _writer = PrintWriter(OUTPUT, false)
inline fun output(block: PrintWriter.() -> Unit) {
    _writer.apply(block).flush()
}

class MutableIntMap<K> : LinkedHashMap<K, Int>() {
    override operator fun get(key: K): Int = super.get(key) ?: 0

    fun increment(key: K, value: Int = 1) {
        this[key] = this[key] + value
    }

    companion object {
        fun <K> mutableIntMapOf(vararg pairs: Pair<K, Int>) =
            MutableIntMap<K>().apply { putAll(pairs) }
    }
}

typealias Pii = Pair<Int, Int>

fun readPii() = readInt() to readInt()
fun readPiis(n: Int) = List(n) { readPii() }

infix fun Int.hasBit(i: Int): Boolean = this and (1 shl i) > 0
infix fun Int.xorBit(i: Int): Int = this xor (1 shl i)
infix fun Long.hasBit(i: Int): Boolean = this and (1L shl i) > 0
infix fun Long.xorBit(i: Int): Long = this xor (1L shl i)

fun largerStackSize(stackSizeMegaBytes: Int = 100, action: () -> Unit) {
    Thread(null, action, "", 1024L * 1024 * stackSizeMegaBytes).apply {
        start()
        join()
    }
}

// #################################################################################################

@JvmInline
value class ModInt private constructor(val value: Int) {
    operator fun plus(other: ModInt) = plus(other.value)
    operator fun plus(other: Int) = from(value + other)
    operator fun minus(other: ModInt) = minus(other.value)
    operator fun minus(other: Int) = from(value - other)
    operator fun times(other: ModInt) = times(other.value)
    operator fun times(other: Int) = from(value.toLong() * other)
    operator fun div(other: ModInt) = times(other.inv())
    operator fun div(other: Int) = div(from(other))

    fun pow(exponent: Int): ModInt {
        var ans = One
        var a = this
        var b = exponent
        while (b > 0) {
            if (b % 2 == 1) ans *= a
            a *= a
            b /= 2
        }
        return ans
    }

    fun inv(): ModInt = pow(MOD - 2)

    override fun toString() = value.toString()

    companion object {
        fun combination(n: Int, k: Int): ModInt {
            check(k in 0..n)
            return (1..k).fold(One) { acc, i -> acc * (n - i + 1) / i }
        }

        fun from(value: Int) = ModInt(value.mod())
        fun from(value: Long) = ModInt(value.mod())
        fun Int.mod() = mod(MOD)
        fun Long.mod() = mod(MOD)
        val Zero = from(0)
        val One = from(1)

        const val MOD = 100
    }
}

fun ask(i: Int, j: Int): ModInt {
    println("? $i $j")
    val a = listOf(31, 41, 59, 26, 53, 58, 97, 93)
//    return ModInt.from(a.subList((1 shl i) * j, (1 shl i) * (j + 1)).sum())//.also { println(it) }
    val value = readInt()
    if (value == -1) System.exit(0)
    return ModInt.from(value)
}

fun solve() {
    val n = readInt()
    val l = readInt()
    val r = readInt()
    fun count(i: Int, j: Int, l: Int, r: Int): Int {
        val i2 = 1 shl i
        val a = i2 * j
        val b = i2 * (j + 1) - 1
        if (l == a && r == b) return 1
        val i1 = 1 shl i - 1
        val m = a + i1
        if (r < m) return count(i - 1, j * 2, l, r)
        if (l >= m) return count(i - 1, j * 2 + 1, l, r)
        var ans = 1
        if (l > a) ans += count(i - 1, j * 2, a, l - 1)
        if (r < b) ans += count(i - 1, j * 2 + 1, r + 1, b)
        return ans.coerceAtMost(count(i - 1, j * 2, l, m - 1) + count(i - 1, j * 2 + 1, m, r))
    }

    fun dfs(i: Int, j: Int, l: Int, r: Int): ModInt {
        val i2 = 1 shl i
        val a = i2 * j
        val b = i2 * (j + 1) - 1
        if (l == a && r == b) return ask(i, j)
        val i1 = 1 shl i - 1
        val m = a + i1
        if (r < m) return dfs(i - 1, j * 2, l, r)
        if (l >= m) return dfs(i - 1, j * 2 + 1, l, r)
        var ans1 = 1
        if (l > a) ans1 += count(i - 1, j * 2, a, l - 1)
        if (r < b) ans1 += count(i - 1, j * 2 + 1, r + 1, b)
        val ans2 = count(i - 1, j * 2, l, m - 1) + count(i - 1, j * 2 + 1, m, r)
        if (ans1 < ans2) {
            var t = ask(i, j)
            if (l > a) t -= dfs(i - 1, j * 2, a, l - 1)
            if (r < b) t -= dfs(i - 1, j * 2 + 1, r + 1, b)
            return t
        }
        return dfs(i - 1, j * 2, l, m - 1) + dfs(i - 1, j * 2 + 1, m, r)
    }

    println("! ${dfs(n, 0, l, r)}")
}

fun main() {
//    repeat(readInt()) { solve() }
    solve()
}

提出情報

コンパイルエラー

Main.kt:113:9: warning: variable 'a' is never used
    val a = listOf(31, 41, 59, 26, 53, 58, 97, 93)
        ^

ジャッジ結果