結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2024-12-31 16:13:55
言語 Scala(Beta)
(3.6.2)
結果
WA  
実行時間 -
コード長 1,955 bytes
コンパイル時間 11,552 ms
コンパイル使用メモリ 277,856 KB
実行使用メモリ 78,604 KB
最終ジャッジ日時 2024-12-31 16:15:26
合計ジャッジ時間 73,519 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 4
other AC * 1 WA * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

import scala.io.StdIn.readLine

type Matrix = Array[Array[Int]] 

def reorderColsByColPerm(s: Matrix, x: Int) =
	val n = s.length
	val t = s.map(_.clone).toArray
	for r <- 0 until n do
		for c <- 0 until n do
			s( r )( t(c)(x) ) = t(r)(c)

def reorderRowsByRowPerm(s: Matrix, y: Int) =
	val n = s.length
	val t = s.map(_.clone).toArray
	for r <- 0 until n do
		for c <- 0 until n do
			s( t(y)(r) )( c ) = t(r)(c)

def selectCol(s: Matrix, x: Int): Array[Int] =
	s.map(_(x)).toArray
	
def selectRow(s: Matrix, y: Int): Array[Int] =
	s(y).clone

def isSame(a: Matrix, b: Matrix): Boolean =
	a.zip(b).forall((x,y) => x.sameElements(y))

def search(b: Matrix, k: Int, t: Matrix, ops: Array[Int]): Boolean =
	if k == 0 then
		return isSame(b, t)
	else
		val n = b.length
		for op <- 0 until 2*n do
			ops(ops.length-k) = op
			val s = t.map(_.clone).toArray
			if op < n then
				reorderColsByColPerm(s,op)
			else
				reorderRowsByRowPerm(s,op-n)
			if search(b, k-1, s, ops) then
				return true
		return false

def solve(n: Int, k: Int, a: Matrix, b: Matrix): List[Int] =
	val ops = new Array[Int](k)
	search(b, k, a, ops)
	
	var ans = List[Int]()
	for op <- ops do
		val p = if op < n then selectCol(a,op) else selectRow(a,op-n)
		var z = op % n
		var tmp = List[Int]()
		var t = (0 until n).toArray
		var w = p.clone
		while !p.sameElements(t) do
			z = p(z)
			tmp = tmp :+ (if op < n then z else (z+n))
			for i <- 0 until n do t(p(i)) = w(i)
			w = t.clone
		ans = tmp.tail ::: ans
		if op < n then
			reorderColsByColPerm(a,op)
		else
			reorderRowsByRowPerm(a,op-n)
	return ans

def readInts() = readLine().split(" ").map(_.toInt-1)

@main def main() =
	val Array(n,k) = readInts().map(_+1)
	val a: Matrix = (1 to n).map(_ => readInts()).toArray
	val b: Matrix = (1 to n).map(_ => readInts()).toArray
	
	val ans = solve(n,k,a,b)
	
	println(ans.length)
	for op <- ans do
		if op < n then
			println("C " + (op+1))
		else
			println("R " + (op+1-n))
0