結果
問題 | No.1598 4×4 Grid |
ユーザー | yakamoto |
提出日時 | 2021-07-10 18:41:37 |
言語 | Kotlin (1.9.23) |
結果 |
AC
|
実行時間 | 751 ms / 4,000 ms |
コード長 | 4,176 bytes |
コンパイル時間 | 16,539 ms |
コンパイル使用メモリ | 465,252 KB |
実行使用メモリ | 181,072 KB |
最終ジャッジ日時 | 2024-07-02 02:44:20 |
合計ジャッジ時間 | 22,643 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 319 ms
55,964 KB |
testcase_01 | AC | 428 ms
106,736 KB |
testcase_02 | AC | 425 ms
106,944 KB |
testcase_03 | AC | 584 ms
106,956 KB |
testcase_04 | AC | 659 ms
145,992 KB |
testcase_05 | AC | 751 ms
181,072 KB |
testcase_06 | AC | 723 ms
180,836 KB |
testcase_07 | AC | 310 ms
51,376 KB |
testcase_08 | AC | 427 ms
106,752 KB |
testcase_09 | AC | 670 ms
146,072 KB |
コンパイルメッセージ
Main.kt:163:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types private inline fun debug(a: LongArray) { ^ Main.kt:167:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types private inline fun debug(a: IntArray) { ^ Main.kt:171:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types private inline fun debug(a: BooleanArray) { ^ Main.kt:175:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types private inline fun toString(a: BooleanArray) = run{a.map { if (it) 1 else 0 }.joinToString("")} ^ Main.kt:177:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types private inline fun debugDim(A: Array<LongArray>) { ^ Main.kt:184:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types private inline fun debugDim(A: Array<IntArray>) { ^ Main.kt:191:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types private inline fun debugDim(A: Array<BooleanArray>) { ^ Main.kt:208:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types private inline fun assert(b: Boolean) = run{if (!b) throw AssertionError()} ^
ソースコード
import java.io.BufferedReaderimport java.io.InputStreamimport java.io.InputStreamReaderimport java.lang.AssertionErrorimport java.util.*import kotlin.math.absimport kotlin.math.maximport kotlin.math.minval MOD = 1_000_000_007class Solver(stream: InputStream, private val out: java.io.PrintWriter) {private val reader = BufferedReader(InputStreamReader(stream), 32768)fun solve() {val K = ni()val D = arrayOf(intArrayOf(-1, 0),intArrayOf(0, 1),intArrayOf(1, 0),intArrayOf(0, -1))val adjMask = IntArray(1 shl 16)for (i in 0 until 16) {val r = i/4val c = i%4for (d in D) {val nr = r + d[0]val nc = c + d[1]if (nr in 0 until 4 && nc in 0 until 4) {val j = nr*4 + ncadjMask[i] = adjMask[i] or (1 shl j)}}}// if (isDebug) {// for (i in 0 until 16) {// debug{"${Integer.toBinaryString(adjMask[i])}"}// }// }val adjCnt = IntArray(1 shl 16)for (bit in 1 until (1 shl 16)) {var i = 0while(bit shr i and 1 == 0) i++val prev = bit xor (1 shl i)val adj = Integer.bitCount(adjMask[i] and prev)val add = Integer.bitCount(adjMask[i]) -2*adjadjCnt[bit] = adjCnt[prev] + add}// debug{"${adjCnt[96]}"}val dp = Array(K + 1){LongArray(1 shl 16)}dp[0][0] = 1for (bit in 0 until (1 shl 16)) {for (k in 0 .. K) {if (dp[k][bit] == 0L) continuefor (i in 0 until 16) {if (bit shr i and 1 == 1) continueval nbit = bit or (1 shl i)val nk = k + adjCnt[nbit]if (nk <= K) dp[nk][nbit] += dp[k][bit]}}}out.println(dp[K][(1 shl 16) - 1])}private val isDebug = try {// なんか本番でエラーでるSystem.getenv("MY_DEBUG") != null} catch (t: Throwable) {false}private var tokenizer: StringTokenizer? = nullprivate fun next(): String {while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {tokenizer = StringTokenizer(reader.readLine())}return tokenizer!!.nextToken()}private fun ni() = next().toInt()private fun nl() = next().toLong()private fun ns() = next()private fun na(n: Int, offset: Int = 0): IntArray {return IntArray(n) { ni() + offset }}private fun nal(n: Int, offset: Int = 0): LongArray {val res = LongArray(n)for (i in 0 until n) {res[i] = nl() + offset}return res}private fun na2(n: Int, offset: Int = 0): Array<IntArray> {val a = Array(2){IntArray(n)}for (i in 0 until n) {for (e in a) {e[i] = ni() + offset}}return a}private inline fun debug(msg: () -> String) {if (isDebug) System.err.println(msg())}/*** コーナーケースでエラー出たりするので、debug(dp[1])のように添え字付きの場合はdebug{}をつかうこと*/private inline fun debug(a: LongArray) {debug { a.joinToString(" ") }}private inline fun debug(a: IntArray) {debug { a.joinToString(" ") }}private inline fun debug(a: BooleanArray) {debug { toString(a) }}private inline fun toString(a: BooleanArray) = run{a.map { if (it) 1 else 0 }.joinToString("")}private inline fun debugDim(A: Array<LongArray>) {if (isDebug) {for (a in A) {debug(a)}}}private inline fun debugDim(A: Array<IntArray>) {if (isDebug) {for (a in A) {debug(a)}}}private inline fun debugDim(A: Array<BooleanArray>) {if (isDebug) {for (a in A) {debug(a)}}}/*** 勝手にimport消されるのを防ぎたい*/private fun hoge() {min(1, 2)max(1, 2)abs(-10)}private inline fun assert(b: Boolean) = run{if (!b) throw AssertionError()}private inline fun assert(b: Boolean, f: () -> String) = run{if (!b) throw AssertionError(f())}}fun main() {val out = java.io.PrintWriter(System.out)Solver(System.`in`, out).solve()out.flush()}