結果
問題 | No.1359 [Zelkova 3rd Tune] 四人セゾン |
ユーザー | da_louis |
提出日時 | 2021-01-22 23:01:22 |
言語 | Kotlin (1.9.23) |
結果 |
AC
|
実行時間 | 1,412 ms / 2,000 ms |
コード長 | 14,052 bytes |
コンパイル時間 | 28,165 ms |
コンパイル使用メモリ | 454,068 KB |
実行使用メモリ | 77,244 KB |
最終ジャッジ日時 | 2023-08-27 21:39:16 |
合計ジャッジ時間 | 117,116 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 335 ms
58,764 KB |
testcase_01 | AC | 332 ms
56,932 KB |
testcase_02 | AC | 328 ms
56,652 KB |
testcase_03 | AC | 1,169 ms
66,684 KB |
testcase_04 | AC | 1,089 ms
66,736 KB |
testcase_05 | AC | 959 ms
67,664 KB |
testcase_06 | AC | 1,166 ms
67,020 KB |
testcase_07 | AC | 1,072 ms
69,620 KB |
testcase_08 | AC | 1,097 ms
69,412 KB |
testcase_09 | AC | 644 ms
61,620 KB |
testcase_10 | AC | 622 ms
63,688 KB |
testcase_11 | AC | 1,125 ms
71,924 KB |
testcase_12 | AC | 1,050 ms
70,356 KB |
testcase_13 | AC | 951 ms
66,392 KB |
testcase_14 | AC | 923 ms
66,080 KB |
testcase_15 | AC | 839 ms
67,844 KB |
testcase_16 | AC | 849 ms
67,804 KB |
testcase_17 | AC | 1,063 ms
75,972 KB |
testcase_18 | AC | 1,082 ms
74,424 KB |
testcase_19 | AC | 1,078 ms
70,424 KB |
testcase_20 | AC | 977 ms
71,396 KB |
testcase_21 | AC | 1,124 ms
72,252 KB |
testcase_22 | AC | 1,064 ms
70,048 KB |
testcase_23 | AC | 977 ms
69,076 KB |
testcase_24 | AC | 1,025 ms
68,412 KB |
testcase_25 | AC | 572 ms
61,288 KB |
testcase_26 | AC | 565 ms
59,540 KB |
testcase_27 | AC | 826 ms
63,852 KB |
testcase_28 | AC | 813 ms
64,044 KB |
testcase_29 | AC | 879 ms
64,396 KB |
testcase_30 | AC | 962 ms
64,964 KB |
testcase_31 | AC | 1,024 ms
66,376 KB |
testcase_32 | AC | 1,053 ms
68,024 KB |
testcase_33 | AC | 992 ms
62,164 KB |
testcase_34 | AC | 925 ms
63,216 KB |
testcase_35 | AC | 1,101 ms
66,120 KB |
testcase_36 | AC | 955 ms
65,112 KB |
testcase_37 | AC | 640 ms
60,208 KB |
testcase_38 | AC | 638 ms
61,604 KB |
testcase_39 | AC | 615 ms
59,680 KB |
testcase_40 | AC | 615 ms
61,328 KB |
testcase_41 | AC | 780 ms
60,720 KB |
testcase_42 | AC | 734 ms
58,780 KB |
testcase_43 | AC | 634 ms
59,272 KB |
testcase_44 | AC | 1,412 ms
73,816 KB |
testcase_45 | AC | 896 ms
64,816 KB |
testcase_46 | AC | 676 ms
59,624 KB |
testcase_47 | AC | 1,200 ms
68,736 KB |
testcase_48 | AC | 980 ms
69,456 KB |
testcase_49 | AC | 1,074 ms
68,056 KB |
testcase_50 | AC | 896 ms
65,364 KB |
testcase_51 | AC | 504 ms
60,044 KB |
testcase_52 | AC | 1,184 ms
71,980 KB |
testcase_53 | AC | 1,374 ms
74,356 KB |
testcase_54 | AC | 1,277 ms
76,064 KB |
testcase_55 | AC | 1,118 ms
75,896 KB |
testcase_56 | AC | 1,097 ms
76,240 KB |
testcase_57 | AC | 1,267 ms
73,252 KB |
testcase_58 | AC | 1,201 ms
73,344 KB |
testcase_59 | AC | 1,110 ms
74,588 KB |
testcase_60 | AC | 1,150 ms
77,244 KB |
testcase_61 | AC | 1,232 ms
73,240 KB |
testcase_62 | AC | 1,214 ms
73,208 KB |
testcase_63 | AC | 1,151 ms
74,232 KB |
testcase_64 | AC | 1,117 ms
75,436 KB |
testcase_65 | AC | 1,251 ms
75,260 KB |
testcase_66 | AC | 1,270 ms
73,500 KB |
testcase_67 | AC | 1,191 ms
75,280 KB |
testcase_68 | AC | 1,128 ms
76,084 KB |
testcase_69 | AC | 1,291 ms
75,088 KB |
testcase_70 | AC | 1,101 ms
74,520 KB |
testcase_71 | AC | 1,078 ms
74,260 KB |
testcase_72 | AC | 1,174 ms
74,984 KB |
testcase_73 | AC | 1,059 ms
69,508 KB |
testcase_74 | AC | 1,113 ms
70,276 KB |
testcase_75 | AC | 1,085 ms
70,256 KB |
testcase_76 | AC | 1,149 ms
69,540 KB |
testcase_77 | AC | 1,192 ms
71,216 KB |
コンパイルメッセージ
Main.kt:19:31: warning: unnecessary non-null assertion (!!) on a non-null receiver of type Long val min = member.min()!! ^ Main.kt:20:31: warning: unnecessary non-null assertion (!!) on a non-null receiver of type Long val max = member.max()!! ^ Main.kt:59: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:92: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:92: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:93: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:125:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead. if (b == '-'.toByte()) { ^ Main.kt:151:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead. if (b == '-'.toByte()) { ^ Main.kt:157:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead. if (b == '.'.toByte()) {
ソースコード
import java.io.ByteArrayInputStream import java.io.ByteArrayOutputStream import java.io.PrintStream fun main() = if (localEnv && execChecker) checker() else contest296b() fun contest296b() = solve() @OptIn(ExperimentalStdlibApi::class) private fun solve() = Messiah_contest296b(MOD).exec { val (n, k, m) = readInt() to readLong() to readInt() val P = readLong(n).sortedArray() val E = readLong(n).sortedArray() val A = readLong(n).sortedArray() val H = readLong(n).sortedArray() val answer = n.indices.map { val member = listOf(P[it], E[it], A[it], H[it]) val min = member.min()!! val max = member.max()!! val unfairness = max - min unfairness.modPow(k, m) }.reduce { acc, l -> (acc + l) % m } println(answer) } 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_contest296b(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_contest296b(MOD).exec { TODO() } @Suppress("ClassName", "unused", "FunctionName", "PropertyName") private class Messiah_contest296b(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 debugln(any: Any): Unit = run { if (localEnv) System.err.println(any) } fun debugln(): Unit = run { if (localEnv) System.err.println() } fun debugln(action: () -> Unit): Unit = run { if (localEnv) action() } fun exec(action: Messiah_contest296b.() -> 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 ////////////////////////////////////////////////// fun Long.invertMod(): Long = invGcd(this).second fun Long.safeMod(): Long = (this % MOD).let { if (it < 0) it + MOD else it } fun Long.modPow(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.modPow(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) } } /** * get characters numeric value. * e.g.: '0' to 0 */ fun Char.toNumericValue(): Int = this - '0' fun Char.caseToIndexedValue(): Int = this - 'a' // fun Char.isLowerCase() = this in 'a'..'z' // // fun Char.isUpperCase() = this in 'A'..'Z' /** * 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): Unit = run { this[i] = kotlin.math.min(this[i], v) } fun IntArray.changeMaxOf(i: Int, v: Int): Unit = run { this[i] = kotlin.math.max(this[i], v) } fun LongArray.changeMinOf(i: Int, v: Long): Unit = run { this[i] = kotlin.math.min(this[i], v) } fun LongArray.changeMaxOf(i: Int, v: Long): Unit = run { this[i] = kotlin.math.max(this[i], 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^)