結果
問題 |
No.2986 Permutation Puzzle
|
ユーザー |
![]() |
提出日時 | 2025-01-23 18:53:53 |
言語 | Standard ML (MLton 20210117) |
結果 |
AC
|
実行時間 | 364 ms / 2,000 ms |
コード長 | 2,632 bytes |
コンパイル時間 | 3,254 ms |
コンパイル使用メモリ | 689,020 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-01-23 18:54:04 |
合計ジャッジ時間 | 9,330 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
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 => []; 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([]) 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); printLine (Int.toString (length ans)); app (printLine o (fn ope => (if ope < n then "C " else "R ") ^ Int.toString ((ope mod n)+1))) ans;