結果

問題 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] }
}
0