結果

問題 No.186 中華風 (Easy)
ユーザー da_louisda_louis
提出日時 2021-02-28 16:35:41
言語 Kotlin
(1.9.23)
結果
AC  
実行時間 365 ms / 2,000 ms
コード長 19,973 bytes
コンパイル時間 28,355 ms
コンパイル使用メモリ 487,664 KB
実行使用メモリ 62,652 KB
最終ジャッジ日時 2024-04-10 18:29:56
合計ジャッジ時間 31,153 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 269 ms
58,844 KB
testcase_01 AC 284 ms
62,516 KB
testcase_02 AC 282 ms
62,652 KB
testcase_03 AC 334 ms
62,504 KB
testcase_04 AC 365 ms
62,452 KB
testcase_05 AC 289 ms
62,428 KB
testcase_06 AC 285 ms
62,412 KB
testcase_07 AC 282 ms
62,516 KB
testcase_08 AC 286 ms
62,488 KB
testcase_09 AC 285 ms
62,520 KB
testcase_10 AC 287 ms
58,844 KB
testcase_11 AC 333 ms
62,452 KB
testcase_12 AC 287 ms
62,520 KB
testcase_13 AC 296 ms
62,520 KB
testcase_14 AC 281 ms
62,460 KB
testcase_15 AC 290 ms
62,444 KB
testcase_16 AC 298 ms
62,440 KB
testcase_17 AC 284 ms
62,412 KB
testcase_18 AC 363 ms
62,628 KB
testcase_19 AC 267 ms
58,860 KB
testcase_20 AC 260 ms
58,860 KB
testcase_21 AC 271 ms
58,876 KB
testcase_22 AC 268 ms
58,896 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:174:13: warning: 'appendln(Int): kotlin.text.StringBuilder /* = java.lang.StringBuilder */' is deprecated. Use appendLine instead. Note that the new method always appends the line feed character '\n' regardless of the system line separator.
            appendln(n)
            ^
Main.kt:207:48: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
    private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
                                               ^
Main.kt:207:62: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
    private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
                                                             ^
Main.kt:208:68: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
    private fun Byte.toNumVal() = if (this.isNumeric()) this - '0'.toByte() else error("$this is not numeric")
                                                                   ^
Main.kt:240:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
        if (b == '-'.toByte()) {
                     ^
Main.kt:266:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
        if (b == '-'.toByte()) {
                     ^
Main.kt:272:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
        if (b == '.'.toByte()) {
                     ^

ソースコード

diff #

import java.io.ByteArrayInputStream
import java.io.ByteArrayOutputStream
import java.io.PrintStream
import java.math.BigInteger

fun main() = if (localEnv && execChecker) checker() else p447()

fun p447() = solve()

@OptIn(ExperimentalStdlibApi::class)
private fun solve() = Messiah_p447(MOD).exec {
    val (x1, y1) = readLong() to readLong()
    val (x2, y2) = readLong() to readLong()
    val (x3, y3) = readLong() to readLong()



    val (v, lcm) = MathLib.crt(longArrayOf(x1, x2, x3), longArrayOf(y1, y2, y3))

    val answer = when (lcm) {
        0L -> -1L
        else -> when {
            listOf(x1, x2, x3).all { it == 0L } -> lcm
            else -> v
        }
    }

    println(answer)
}

/**
 * MathLib.
 *
 * convert from [AtCoderLibraryForJava - MathLib](https://github.com/NASU41/AtCoderLibraryForJava/blob/132179385293fd6c0d522d73f3f48435967fffcb/Math/MathLib.java#L4)
 */
private object MathLib {
    /**
     * xをmで割った余りを返す.
     */
    fun safeMod(x: Long, m: Long): Long {
        val vx = x % m
        return if (vx < 0) vx + m else vx
    }

    fun invGcd(a: Long, b: Long): LongArray {
        var va = a
        va = safeMod(va, b)
        if (va == 0L) return longArrayOf(b, 0)
        var s = b
        var t = va
        var m0: Long = 0
        var m1: Long = 1
        while (t > 0) {
            val u = s / t
            s -= t * u
            m0 -= m1 * u
            var tmp = s
            s = t
            t = tmp
            tmp = m0
            m0 = m1
            m1 = tmp
        }
        if (m0 < 0) m0 += b / s
        return longArrayOf(s, m0)
    }

    /**
     * xのn乗をmで割った余りを返す.
     */
    fun powMod(x: Long, n: Long, m: Int): Long {
        var vx = x
        var vn = n
        assert(vn >= 0)
        assert(m >= 1)
        if (m == 1) return 0L
        vx = safeMod(vx, m.toLong())
        var ans = 1L
        while (vn > 0) {
            if (vn and 1 == 1L) ans = ans * vx % m
            vx = vx * vx % m
            vn = vn ushr 1
        }
        return ans
    }

    fun crt(r: LongArray, m: LongArray): LongArray {
        assert(r.size == m.size)
        val n = r.size
        var r0: Long = 0
        var m0: Long = 1
        for (i in 0 until n) {
            assert(1 <= m[i])
            var r1 = safeMod(r[i], m[i])
            var m1 = m[i]
            if (m0 < m1) {
                var tmp = r0
                r0 = r1
                r1 = tmp
                tmp = m0
                m0 = m1
                m1 = tmp
            }
            if (m0 % m1 == 0L) {
                if (r0 % m1 != r1) return longArrayOf(0, 0)
                continue
            }
            val ig = invGcd(m0, m1)
            val g = ig[0]
            val im = ig[1]
            val u1 = m1 / g
            if ((r1 - r0) % g != 0L) return longArrayOf(0, 0)
            val x = (r1 - r0) / g % u1 * im % u1
            r0 += x * m0
            m0 *= u1
            if (r0 < 0) r0 += m0
            //System.err.printf("%d %d\n", r0, m0);
        }
        return longArrayOf(r0, m0)
    }

    fun floorSum(n: Long, m: Long, a: Long, b: Long): Long {
        var va = a
        var vb = b
        var ans: Long = 0
        if (va >= m) {
            ans += (n - 1) * n * (va / m) / 2
            va %= m
        }
        if (vb >= m) {
            ans += n * (vb / m)
            vb %= m
        }
        val yMax = (va * n + vb) / m
        val xMax = yMax * m - vb
        if (yMax == 0L) return ans
        ans += (n - (xMax + va - 1) / va) * yMax
        ans += floorSum(yMax, va, m, (va - xMax % va) % va)
        return ans
    }
}

private const val MOD = 1_000_000_007

// region kokokara template dayo (^o^)
private const val execChecker = false
private val localEnv =
        runCatching { "ENABLE_DEBUG_MODE_FOR_COMPETITIVE_PROGRAMING" in System.getenv() }.getOrNull() ?: false

private fun checker() = Messiah_p447(MOD).exec {
    debugln("#######################################################")
    debugln("###############  executing check mode.  ###############")
    debugln("#######################################################")

    fun getOutPut(input: String, action: () -> Unit): String {
        System.setIn(ByteArrayInputStream(input.toByteArray()))
        val sysOut = ByteArrayOutputStream()
        System.setOut(PrintStream(sysOut))
        action()
        return sysOut.toString()
    }

    val wrongCases = mutableSetOf<List<String>>()

    while (wrongCases.size < 10) {
        /*
        examples
        val randomString = (1..20).map { ('a'..'z').random() }.joinToString("")
        val randomNum = Random.nextInt(0,2000)
         */
        val n = 0

        val input = buildString {
            appendln(n)
        }

        val solve = getOutPut(input, ::solve)
        val greedy = getOutPut(input, ::greedy)

        if (solve != greedy && wrongCases.add(listOf(solve, greedy))) {
            debugln("#################### wrong case: ${wrongCases.size} ####################")
            debugln("input:")
            debugln(input)
            debugln("solve:")
            debugln(solve)
            debugln("greedy:")
            debugln(greedy)
        }
    }
}

private fun greedy() = Messiah_p447(MOD).exec {
    TODO()
}

@Suppress("ClassName", "unused", "FunctionName", "PropertyName")
private class Messiah_p447(private val mod: Int) {
    //////////////////////////////////////////////////
    // IO
    //////////////////////////////////////////////////
    private val input = System.`in`
    private val buffer = ByteArray(1024)
    private var pointer = 0
    private var bufferLength = 0
    private val sb = StringBuilder()
    private fun Byte.isPrintable() = this in 33..126
    private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
    private fun Byte.toNumVal() = if (this.isNumeric()) this - '0'.toByte() else error("$this is not numeric")
    private val lineSeparator: String = System.lineSeparator()

    private fun hasNextByte(): Boolean {
        return if (pointer < bufferLength) true else {
            pointer = 0
            bufferLength = input.read(buffer)
            bufferLength > 0
        }
    }

    private fun readByte(): Byte = if (hasNextByte()) buffer[pointer++] else -1
    private fun skipUnprintable() = run { while (hasNextByte() && !buffer[pointer].isPrintable()) pointer++ }
    private fun hasNext(): Boolean = run { skipUnprintable() }.run { hasNextByte() }
    private fun hasNextOrError() = if (!hasNext()) error("has no next element.") else Unit

    fun readString(): String {
        hasNextOrError()
        val sb = StringBuilder()
        var b = readByte()
        while (b.isPrintable()) {
            sb.appendCodePoint(b.toInt())
            b = readByte()
        }
        return sb.toString()
    }

    fun readLong(): Long {
        hasNextOrError()
        var n = 0L
        var negative = false
        var b = readByte()
        if (b == '-'.toByte()) {
            negative = true
            b = readByte()
        }
        if (!b.isNumeric()) error("$b is not numeric.")
        while (true) {
            when {
                b.isNumeric() -> n = n * 10 + b.toNumVal()
                b.toInt() == -1 || !b.isPrintable() -> return if (negative) -n else n
                else -> error("failed to parse. [n=$n, b=$b]")
            }
            b = readByte()
        }
    }

    fun readInt() = readLong()
            .let { if (it in Int.MIN_VALUE..Int.MAX_VALUE) it.toInt() else error("$it is not in range of Int.") }

    fun readIntAsIndex() = readInt().dec()

    fun readDouble(): Double {
        hasNextOrError()
        var n = 0.0
        var div = 1.0
        var negative = false
        var b = readByte()
        if (b == '-'.toByte()) {
            negative = true
            b = readByte()
        }
        do n = n * 10 + b.toNumVal()
        while (run { b = readByte() }.run { b.isNumeric() })
        if (b == '.'.toByte()) {
            while (run { b = readByte() }.run { b.isNumeric() })
                n += b.toNumVal() / (run { div *= 10 }.run { div })
        }
        return if (negative) -n else n
    }

    fun readString(size: Int): Array<String> = Array(size) { readString() }

    @Suppress("UNUSED_PARAMETER")
    fun readChars(h: Int, w: Int): Array<CharArray> = Array(h) { readString().toCharArray() }
    fun readLong(size: Int): LongArray = LongArray(size) { readLong() }
    fun readLong(h: Int, w: Int): Array<LongArray> = Array(h) { readLong(w) }
    fun readInt(size: Int): IntArray = IntArray(size) { readInt() }
    fun readInt(h: Int, w: Int): Array<IntArray> = Array(h) { readInt(w) }
    fun readIntAsIndex(size: Int): IntArray = IntArray(size) { readIntAsIndex() }
    fun readIntAsIndex(h: Int, w: Int): Array<IntArray> = Array(h) { readIntAsIndex(w) }
    fun readDouble(size: Int): DoubleArray = DoubleArray(size) { readDouble() }
    fun readDouble(h: Int, w: Int): Array<DoubleArray> = Array(h) { readDouble(w) }
    fun readBooleanWithSeparator(size: Int, trueElement: String): BooleanArray =
            BooleanArray(size) { readString() == trueElement }

    fun readBooleanWithSeparator(h: Int, w: Int, trueElement: String): Array<BooleanArray> =
            Array(h) { readBooleanWithSeparator(w, trueElement) }

    @Suppress("UNUSED_PARAMETER")
    fun readBooleanWithoutSeparator(size: Int, trueElement: Char): BooleanArray =
            readString().map { it == trueElement }.toBooleanArray()

    fun readBooleanWithoutSeparator(h: Int, w: Int, trueElement: Char): Array<BooleanArray> =
            Array(h) { readBooleanWithoutSeparator(w, trueElement) }

    fun println(): Unit = run { sb.append(lineSeparator) }
    fun print(any: Any): Unit = run { sb.append(any.toString()) }
    fun println(any: Any): Unit = run { sb.append(any.toString() + lineSeparator) }
    fun flush() = run { kotlin.io.println(sb); sb.clear() }
    fun debug(any: Any): Unit = run { if (localEnv) System.err.print(any) }
    fun debugln(any: Any): Unit = run { if (localEnv) System.err.println(any) }
    fun debugln(): Unit = run { if (localEnv) System.err.println() }
    fun debugExec(action: () -> Unit): Unit = run { if (localEnv) action() }

    fun exec(action: Messiah_p447.() -> Unit) {
        var t: Throwable? = null
        Thread(null, { action() }, "solve", 128 * 1024 * 1024)
                .apply { setUncaughtExceptionHandler { _, t1 -> t = t1 } }
                .apply { start() }.join()
        t?.let { throw it }
        kotlin.io.print(sb)
    }

    fun readLine(): Nothing = error("readLine is disabled.")

    //////////////////////////////////////////////////
    // MOD
    //////////////////////////////////////////////////
    private val modIsPrime: Boolean = MOD.toBigInteger().isProbablePrime(100)

    fun Long.invertMod(): Long = if (modIsPrime) this.powMod(MOD - 2L) else invGcd(this).second
    fun Long.safeMod(): Long = (this % MOD).let { if (it < 0) it + MOD else it }
    fun Long.plusMod(other: Long): Long = this.plus(other).safeMod()
    fun Long.minusMod(other: Long): Long = this.minus(other).safeMod()
    fun Long.timesMod(other: Long): Long = this.times(other).safeMod()
    fun Long.divMod(other: Long): Long = this.times(other.invertMod()).safeMod()

    fun Long.powMod(p: Long): Long {
        var x = this % MOD
        var y = p
        var result = 1L
        while (y > 0) {
            if (y % 2 == 1L) result = (result * x) % MOD
            y = y shr 1
            x = (x * x) % MOD
        }
        return result
    }

    fun Long.powMod(p: Long, m: Int): Long {
        var x = this % m
        var y = p
        var result = 1L
        while (y > 0) {
            if (y % 2 == 1L) result = (result * x) % m
            y = y shr 1
            x = (x * x) % m
        }
        return result
    }

    fun invGcd(a: Long): Pair<Long, Long> {
        val am = a.safeMod()
        if (a == 0L) return MOD.toLong() to 0L
        var s = MOD.toLong()
        var t = am
        var m0 = 0L
        var m1 = 1L
        while (t != 0L) {
            val u = s / t
            s -= t * u
            m0 -= m1 * u

            var temp = s
            s = t
            t = temp
            temp = m0
            m0 = m1
            m1 = temp
        }
        if (m0 < 0) m0 += MOD / s
        return s to m0
    }

    //////////////////////////////////////////////////
    // Misc
    //////////////////////////////////////////////////
    /**
     * `n.indices()` is sugar syntax of `0 until n`.
     */
    val Int.indices: IntRange get() = 0 until this

    /**
     * `[index] in [this]` is sugar syntax of `index in 0 until [this]`.
     */
    operator fun Int.contains(index: Int): Boolean = index in this.indices

    /**
     * `[this].mapIndices { transform }` is sugar syntax of `(0 until [this]).map{ transform(it) }`.
     */
    inline fun <R> Int.mapIndices(transform: (Int) -> R): List<R> = this.indices.map(transform)

    /**
     * `[this].mapIndices(x) { transform }` is sugar syntax of
     * `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`.
     */
    inline fun <R> Int.mapIndices(x: Int, transform: (Int, Int) -> R): List<List<R>> =
            this.mapIndices { y1 -> x.mapIndices { x1 -> transform(y1, x1) } }

    /**
     * `[this].mapIndices(x) { transform }` is sugar syntax of
     * `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`.
     */
    inline fun <R> Int.flatMapIndices(x: Int, transform: (Int, Int) -> R): List<R> =
            this.indices.flatMap { y1 -> x.mapIndices { x1 -> transform(y1, x1) } }

    /**
     * `[this].forEachIndices { transform }` is sugar syntax of `(0 until [this]).map{ transform(it) }`.
     */
    inline fun Int.forEachIndices(transform: (Int) -> Unit): Unit = this.indices.forEach(transform)

    /**
     * `[this].forEachIndices(x) { transform }` is sugar syntax of
     * `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`.
     */
    inline fun Int.forEachIndices(x: Int, transform: (Int, Int) -> Unit): Unit =
            this.forEachIndices { y1 -> x.forEachIndices { x1 -> transform(y1, x1) } }

    /**
     * 正の方向へ丸める割り算
     */
    fun Int.ceilDiv(b: Int): Int = this.also { check(b != 0) }.run {
        when {
            b < 0 -> (-this).ceilDiv(-b)
            this > 0 -> ((this + b - 1) / b)
            else -> (this / b)
        }
    }

    /**
     * 負の方向へ丸める割り算
     */
    fun Int.floorDiv(b: Int): Int = -(-this).ceilDiv(b)

    /**
     * 正の方向へ丸める割り算
     */
    fun Long.ceilDiv(b: Long): Long = this.also { check(b != 0L) }.run {
        when {
            b < 0 -> (-this).ceilDiv(-b)
            this > 0 -> ((this + b - 1) / b)
            else -> (this / b)
        }
    }

    /**
     * 負の方向へ丸める割り算
     */
    fun Long.floorDiv(b: Long): Long = -(-this).ceilDiv(b)

    /**
     * 0から離れている方向の[b]の倍数へ切り上げる
     */
    fun Long.ceilMultipleOf(b: Long): Long = this / b * b + if (this % b == 0L) 0L else b

    /**
     * get characters numeric value.
     * e.g.: '0' to 0
     */
    fun Char.toNumericValue(): Int = this - '0'

    fun Char.caseToIndexedValue(): Int = this - 'a'

    fun String.toPoweredLong(p: Int): Long {
        check(this.isNotBlank())
        if (this[0] == '-') return -this.drop(1).toPoweredLong(p)
        var mulI = 1L
        repeat(p) { mulI *= 10 }
        val i = this.indexOf('.').takeIf { it != -1 } ?: return this.toLong() * mulI
        var mulD = 1L
        repeat(p - this.length + i + 1) { mulD *= 10 }
        return this.slice(0 until i).toLong() * mulI + this.slice(i + 1..this.lastIndex).toLong() * mulD
    }

    fun String.toBigIntegerWithBase(base: BigInteger): BigInteger {
        var sum = BigInteger.ZERO
        var bs = BigInteger.ONE
        for (c in this.reversed()) {
            sum += bs * (Character.getNumericValue(c)).toBigInteger()
            bs *= base
        }
        return sum
    }

    /**
     * make triple. e.g.:`1 to 2 to 3`
     */
    infix fun <A, B, C> Pair<A, B>.to(c: C): Triple<A, B, C> = Triple(this.first, this.second, c)

    fun YesNo(b: Boolean): String = if (b) Yes else No
    val Yes = "Yes"
    val No = "No"
    fun YES_NO(b: Boolean): String = if (b) YES else NO
    val YES = "YES"
    val NO = "NO"

    fun IntArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
    fun LongArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
    fun CharArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
    fun <T> Array<T>.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
    fun <T> MutableList<T>.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }

    fun IntArray.changeMinOf(i: Int, v: Int): Boolean = run { if (this[i] > v) run { this[i] = v; true } else false }
    fun IntArray.changeMaxOf(i: Int, v: Int): Boolean = run { if (this[i] < v) run { this[i] = v; true } else false }
    fun LongArray.changeMinOf(i: Int, v: Long): Boolean = run { if (this[i] > v) run { this[i] = v; true } else false }
    fun LongArray.changeMaxOf(i: Int, v: Long): Boolean = run { if (this[i] < v) run { this[i] = v; true } else false }
    fun Array<IntArray>.changeMinOf(i: Int, j: Int, v: Int): Boolean = this[i].changeMinOf(j, v)
    fun Array<IntArray>.changeMaxOf(i: Int, j: Int, v: Int): Boolean = this[i].changeMaxOf(j, v)
    fun Array<LongArray>.changeMinOf(i: Int, j: Int, v: Long): Boolean = this[i].changeMinOf(j, v)
    fun Array<LongArray>.changeMaxOf(i: Int, j: Int, v: Long): Boolean = this[i].changeMaxOf(j, v)
    fun Array<Array<IntArray>>.changeMinOf(i: Int, j: Int, k: Int, v: Int): Boolean = this[i].changeMinOf(j, k, v)
    fun Array<Array<IntArray>>.changeMaxOf(i: Int, j: Int, k: Int, v: Int): Boolean = this[i].changeMaxOf(j, k, v)
    fun Array<Array<LongArray>>.changeMinOf(i: Int, j: Int, k: Int, v: Long): Boolean = this[i].changeMinOf(j, k, v)
    fun Array<Array<LongArray>>.changeMaxOf(i: Int, j: Int, k: Int, v: Long): Boolean = this[i].changeMaxOf(j, k, v)

    /**
     * same usage as `IntArray.scan`, but it will faster than that.
     */
    inline fun IntArray.scanArray(initial: Int, operation: (acc: Int, Int) -> Int): IntArray {
        val accumulator = IntArray(this.size + 1).apply { this[0] = initial }
        for (i in this.indices) accumulator[i + 1] = operation(accumulator[i], this[i])
        return accumulator
    }

    /**
     * same usage as `LongArray.scan`, but it will faster than that.
     */
    inline fun LongArray.scanArray(initial: Long, operation: (acc: Long, Long) -> Long): LongArray {
        val accumulator = LongArray(this.size + 1).apply { this[0] = initial }
        for (i in this.indices) accumulator[i + 1] = operation(accumulator[i], this[i])
        return accumulator
    }

    /**
     * same usage as `IntArray.scanReduce`, but it will faster than that.
     */
    inline fun IntArray.scanReduceArray(operation: (acc: Int, Int) -> Int): IntArray {
        val accumulator = IntArray(this.size).apply { this[0] = this@scanReduceArray[0] }
        for (i in 1..this.lastIndex) accumulator[i] = operation(accumulator[i - 1], this[i])
        return accumulator
    }

    /**
     * same usage as `LongArray.scanReduce`, but it will faster than that.
     */
    inline fun LongArray.scanReduceArray(operation: (acc: Long, Long) -> Long): LongArray {
        val accumulator = LongArray(this.size).apply { this[0] = this@scanReduceArray[0] }
        for (i in 1..this.lastIndex) accumulator[i] = operation(accumulator[i - 1], this[i])
        return accumulator
    }
}
// endregion kokomade template dayo (^o^)
0