結果
問題 | No.1759 Silver Tour |
ユーザー | yudedako |
提出日時 | 2022-01-10 14:26:16 |
言語 | Kotlin (1.9.23) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,136 bytes |
コンパイル時間 | 17,274 ms |
コンパイル使用メモリ | 462,052 KB |
実行使用メモリ | 69,004 KB |
最終ジャッジ日時 | 2024-04-26 20:07:34 |
合計ジャッジ時間 | 34,543 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 321 ms
55,532 KB |
testcase_01 | AC | 296 ms
51,668 KB |
testcase_02 | AC | 323 ms
55,540 KB |
testcase_03 | AC | 603 ms
69,004 KB |
testcase_04 | AC | 320 ms
55,232 KB |
testcase_05 | AC | 296 ms
51,724 KB |
testcase_06 | AC | 321 ms
55,568 KB |
testcase_07 | AC | 322 ms
55,588 KB |
testcase_08 | AC | 289 ms
51,908 KB |
testcase_09 | AC | 324 ms
55,524 KB |
testcase_10 | AC | 326 ms
55,576 KB |
testcase_11 | AC | 320 ms
55,564 KB |
testcase_12 | AC | 327 ms
55,640 KB |
testcase_13 | AC | 327 ms
55,532 KB |
testcase_14 | AC | 323 ms
55,592 KB |
testcase_15 | AC | 331 ms
55,668 KB |
testcase_16 | AC | 325 ms
55,828 KB |
testcase_17 | AC | 334 ms
55,668 KB |
testcase_18 | AC | 298 ms
51,944 KB |
testcase_19 | AC | 331 ms
55,724 KB |
testcase_20 | AC | 324 ms
55,660 KB |
testcase_21 | AC | 337 ms
55,964 KB |
testcase_22 | AC | 317 ms
55,676 KB |
testcase_23 | AC | 323 ms
55,612 KB |
testcase_24 | AC | 322 ms
55,712 KB |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | AC | 326 ms
55,580 KB |
testcase_28 | WA | - |
testcase_29 | AC | 299 ms
52,056 KB |
testcase_30 | WA | - |
testcase_31 | AC | 316 ms
55,532 KB |
testcase_32 | AC | 316 ms
55,496 KB |
testcase_33 | AC | 320 ms
55,540 KB |
testcase_34 | AC | 592 ms
66,712 KB |
testcase_35 | AC | 294 ms
51,644 KB |
testcase_36 | AC | 490 ms
62,356 KB |
testcase_37 | AC | 329 ms
55,640 KB |
testcase_38 | AC | 345 ms
57,104 KB |
testcase_39 | AC | 416 ms
57,732 KB |
testcase_40 | AC | 344 ms
55,764 KB |
testcase_41 | AC | 353 ms
55,916 KB |
testcase_42 | AC | 572 ms
60,688 KB |
testcase_43 | AC | 414 ms
57,396 KB |
ソースコード
import kotlin.math.absoluteValue fun solve(height: Int, width: Int, mod: Int): Int { if (height == 1) { return if (width == 1) 1 else 0 } if (height % 2 == 1) { return 0 } val endState = (1L shl width) - 1 fun Long.lastBit(): Long { return (inv() + 1) and this } fun calcPattern(firstLine: Boolean, column: Int, firstLineState: Long, secondLineState: Long): IntArray? { val both = endState xor (firstLineState and secondLineState) if (both != 0L && (both.lastBit() + both).let { it.lastBit() != it }) { return null } return if (secondLineState == endState) { check(!firstLine && firstLineState == endState) val result = IntArray(width).also { it[column] = 1 } result }else { val result = IntArray(width) var hasPath = false if (firstLine) { for (dc in -1 .. 1) { val c = column + dc if (c !in 0 until width) continue if ((secondLineState shr c) and 1 == 1L) continue val next = calcPattern(!firstLine, c, firstLineState, secondLineState or (1L shl c)) ?: continue hasPath = true for (i in 0 until width) { result[i] = (result[i] + next[i]) % mod } } } else { for (dc in -1 .. 1 step 2) { val c = column + dc if (c !in 0 until width) continue if ((firstLineState shr c) and 1 == 1L) continue val next = calcPattern(!firstLine, c, firstLineState or (1L shl c), secondLineState) ?: continue hasPath = true for (i in 0 until width) { result[i] = (result[i] + next[i]) % mod } } } if (hasPath) result else null } } val pattern = List(width){(calcPattern(true, it, 1L shl it, 0L) ?: IntArray(width)).toList() } operator fun List<List<Int>>.times(right: List<List<Int>>): List<List<Int>> { require(this[0].size == right.size) val result = mutableListOf<List<Int>>() for (i in indices) { val line = mutableListOf<Int>() for (j in right[i].indices) { var value = 0L for (k in right.indices) { value += this[i][k].toLong() * right[k][j] % mod } line.add((value % mod).toInt()) } result.add(line) } return result } val mid = List(width){r -> List(width){c -> if ((r - c).absoluteValue <= 1) 1 else 0} } val result = listOf(List(width){1}) * (1 until height / 2).fold(pattern){ left, _ -> left * mid * pattern} return result.flatten().fold(0){acc, v -> (acc + v) % mod } } fun main() { val (height, width, mod) = readLine()!!.trim().split(' ').map(String::toInt) val result = solve(height, width, mod) println(result) }