結果

問題 No.2986 Permutation Puzzle
コンテスト
ユーザー ID 21712
提出日時 2025-01-23 18:29:28
言語 Standard ML
(MLton 20210117)
結果
AC  
実行時間 391 ms / 2,000 ms
コード長 2,660 bytes
コンパイル時間 4,681 ms
コンパイル使用メモリ 689,280 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-01-23 18:29:42
合計ジャッジ時間 11,489 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

fun rFindMapi 0 f = f 0
 | rFindMapi i f = let val res = f i in if Option.isSome res then res else rFindMapi (i-1) f end;

fun rFindi n f = rFindMapi n (fn i => if f i then SOME(i) else NONE);

fun unfold f s = case  f s of SOME(a,b) => b :: unfold f a | NONE => nil;

fun copyMatrix m = Array2.tabulate Array2.RowMajor (Array2.nRows m, Array2.nCols m, fn (r,c) => Array2.sub (m,r,c));

fun reorderColsByColPerm (s,x) = let
		val t = copyMatrix s
		val rt = {base=t,col=0,row=0,nrows=NONE,ncols=NONE} 
	in
		Array2.appi Array2.RowMajor (fn (r,c,e) => Array2.update (s,r,Array2.sub (t,c,x),e)) rt
	end;

fun reorderRowsByRowPerm (s,y) = let
		val t = copyMatrix s
		val rt = {base=t,col=0,row=0,nrows=NONE,ncols=NONE} 
	in
		Array2.appi Array2.RowMajor (fn (r,c,e) => Array2.update (s,Array2.sub (t,y,r),c,e)) rt
	end;
	
fun isSameM (n,a,b) = not (Option.isSome (rFindi (n-1) (fn r => Option.isSome (rFindi (n-1) (fn c => Array2.sub (a,r,c) <> Array2.sub (b,r,c))))));

fun isSameA (n,a,b) = not (Option.isSome (rFindi (n-1) (fn i => Array.sub (a,i) <> Array.sub (b,i))));

fun search (n,b,0,t) = if isSameM (n,b,t) then SOME(nil) else NONE
 | search (n,b,k,t) = let
		fun find ope = let
			val s = copyMatrix t
			val () = if ope < n then reorderColsByColPerm (s,ope) else reorderRowsByRowPerm (s,ope-n)
		in
			Option.map (fn tail => ope :: tail) (search (n,b,k-1,s))
		end
	in
		rFindMapi (2*n-1) find
	end;

fun selectCol (n,s,x) = Array.tabulate (n, fn r => Array2.sub (s,r,x));

fun selectRow (n,s,y) = Array.tabulate (n, fn c => Array2.sub (s,y,c));

fun solve (n,k,a,b) = let
		val opes = valOf (search (n, b, k, a))
		fun f ope = let
			val perm = if ope < n then selectCol (n,a,ope) else selectRow (n,a,ope-n)
			val () = if ope < n then reorderColsByColPerm (a,ope) else reorderRowsByRowPerm (a,ope-n)
			fun uff (z0,t0) = let
				val z1 = Array.sub (perm,z0)
				val zz = z1 + (ope div n) * n
				val t1 = Array.array (n,0)
				val () = Array.appi (fn (i,e) => Array.update (t1,e,Array.sub (t0,i))) perm
			in
				if isSameA (n,perm,t1) then NONE else SOME(((z1,t1),zz))
			end
		in
			unfold uff (ope mod n, perm)
		end
	in
		(List.concat o rev) (map f opes)
	end;

fun readInt () = valOf (TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn);

fun readMatrix n = Array2.tabulate Array2.RowMajor (n,n, fn (_,_) => readInt () - 1);

fun printLine s = print (s ^ "\n");

val n = readInt ();
val k = readInt ();
val a = readMatrix n;
val b = readMatrix n;
val ans = solve (n, k, a, b);
val () = printLine (Int.toString (length ans));
val () = List.app (printLine o (fn ope => (if ope < n then "C " else "R ") ^ Int.toString ((ope mod n)+1))) ans;
0