Submission #54185405

---

Source Code Expand

import java.io.*
import java.util.*
import java.util.function.IntPredicate
import kotlin.collections.*
import kotlin.system.exitProcess

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()
    }
}

val LOCAL = System.getProperty("ONLINE_JUDGE") == null

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

val A = mutableListOf(0, -1, 10, 1)

fun compare(i: Int, j: Int): Boolean {
    println("? $i $j")
    if (LOCAL) return A[i] < A[j]
    val ans = readInt()
    if (ans == -1) {
        exitProcess(1)
    }
    return ans == 1
}

fun mergeSort(a: List<Int>): List<Int> {
    if (a.size <= 1) return a
    val x = mergeSort(a.subList(0, a.size / 2))
    val y = mergeSort(a.subList(a.size / 2, a.size))
    return buildList {
        var i = 0
        var j = 0
        while (i < x.size || j < y.size) {
            if (i < x.size && (j == y.size || compare(x[i], y[j]))) add(x[i++])
            else add(y[j++])
        }
    }
}

fun sort(n: Int): List<Int> {
    fun dfs(a: List<Int>): List<Int> {
        if (a.isEmpty()) return a
        val p = a.random()
        val l = mutableListOf<Int>()
        val r = mutableListOf<Int>()
        for (i in a) if (i != p) {
            if (compare(i, p)) {
                l += i
            } else {
                r += i
            }
        }
        return dfs(l) + p + dfs(r)
    }
    return mergeSort((1..n).toList())
}

fun addition(i: Int, j: Int): Int {
    println("+ $i $j")
    if (LOCAL) {
        A += A[i] + A[j]
        return A.lastIndex
    }
    val ans = readInt()
    if (ans == -1) {
        exitProcess(1)
    }
    return ans
}

/** The upper bound of [low, high], which `predicate.test(it)` is true. */
fun upperBound(low: Int, high: Int, predicate: IntPredicate): Int? {
    if (low > high) return null
    var l = low
    var h = high
    while (l < h) {
        val m = (l + h + 1) / 2
        if (predicate.test(m)) {
            l = m
        } else {
            h = m - 1
        }
    }
    return l.takeIf(predicate::test)
}

fun sum(a: List<Int>): List<Int> {
    val b = a.subList(1, a.lastIndex).toMutableList()
    val c = addition(a.first(), a.last())
    val i = upperBound(0, b.lastIndex) {
        compare(b[it], c)
    }
    b.add((i ?: -1) + 1, c)
    return b
}

fun solve() {
    val n = readInt()
    var a = sort(n)
    while (a.size > 1) {
        a = sum(a)
    }
    println("!")
}

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

Submission Info

Judge Result