結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2024-12-22 23:08:00
言語 Kotlin
(2.1.0)
結果
AC  
実行時間 678 ms / 2,000 ms
コード長 2,212 bytes
コンパイル時間 18,155 ms
コンパイル使用メモリ 460,116 KB
実行使用メモリ 92,088 KB
最終ジャッジ日時 2024-12-22 23:08:43
合計ジャッジ時間 39,043 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:43:6: warning: identity equality for arguments of types Int and Int is deprecated
	if (k === 0) {
     ^

ソースコード

diff #
プレゼンテーションモードにする

private fun readInts() = readln().split(" ").map { it.toInt() }.toIntArray()
fun main() {
    val (n, k) = readInts()
    val a = Array(n) { _ -> readInts() }
    val b = Array(n) { _ -> readInts() }
    val ans = solve(n, k, a, b);
    println("${ans.count()}")
    ans.forEach { op -> 
        if (op < n) {
            println("C ${op+1}")
        } else {
            println("R ${op+1-n}")
        }
    }
}
fun solve(n: Int, k: Int, a: Array<IntArray>, b: Array<IntArray>): IntArray {
    val ops = IntArray(k)
    search(b, k, a, ops)
    ops.reverse()
    val ans = mutableListOf<Int>()
    ops.forEach { op -> 
        val p = if (op < n) selectCol(a,op) else selectRow(a,op-n)
        if (op < n) {
            reorderColsByColPerm(a, op)
        } else {
            reorderRowsByRowPerm(a, op-n)
        }
        val tmp = mutableListOf<Int>()
        val cnt = cycle(p) - 1
        var z = op % n
        for (i in 1..cnt) {
            z = p[z]-1
            tmp.add(if (op < n) z else (z+n))
        }
        ans.addAll(0, tmp)
    }
    return ans.toIntArray()
}
fun search(b: Array<IntArray>, k: Int, t: Array<IntArray>, v: IntArray): Boolean {
    if (k === 0) {
        return t.contentDeepEquals(b)
    }
    for (i in b.indices) {
        v[k-1] = i
        val s1 = Array(t.count()) { e -> t[e].copyOf() }
        reorderColsByColPerm(s1, i)
        if (search(b, k-1, s1, v)) {
            return true
        }
        v[k-1] = i + b.count()
        val s2 = Array(t.count()) { e -> t[e].copyOf() }
        reorderRowsByRowPerm(s2, i)
        if (search(b, k-1, s2, v)) {
            return true
        }
    }
    return false
}
fun cycle(p: IntArray): Int {
    var t = p.copyOf()
    var w = p.copyOf()
    var cnt = 0
    while (true) {
        cnt++
        for (i in p.indices) {
            t[ p[i]-1 ] = w[i]
        }
        if (p.contentEquals(t)) {
            return cnt
        }
        w = t.copyOf()
    }
}
fun reorderColsByColPerm(s: Array<IntArray>, x: Int) {
    val t = Array(s.count()) { i -> s[i].copyOf() }
    for (r in t.indices) {
        for (c in t.indices) {
            s[ r ][ t[c][x]-1 ] = t[r][c]
        }
    }
}
fun reorderRowsByRowPerm(s: Array<IntArray>, y: Int) {
    val t = Array(s.count()) { i -> s[i].copyOf() }
    for (r in t.indices) {
        for (c in t.indices) {
            s[ t[y][r]-1 ][ c ] = t[r][c]
        }
    }
}
fun selectCol(s: Array<IntArray>, x: Int): IntArray  {
    return IntArray(s.count()) { r -> s[r][x] }
}
fun selectRow(s: Array<IntArray>, y: Int): IntArray  {
    return IntArray(s.count()) { c -> s[y][c] }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0