結果
問題 | No.2986 Permutation Puzzle |
ユーザー | ID 21712 |
提出日時 | 2024-12-24 01:27:15 |
言語 | F# (F# 4.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,749 bytes |
コンパイル時間 | 10,138 ms |
コンパイル使用メモリ | 199,796 KB |
実行使用メモリ | 62,288 KB |
最終ジャッジ日時 | 2024-12-24 01:28:17 |
合計ジャッジ時間 | 59,825 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 393 ms
37,008 KB |
testcase_01 | AC | 395 ms
36,888 KB |
testcase_02 | AC | 399 ms
36,844 KB |
testcase_03 | TLE | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | AC | 403 ms
37,080 KB |
testcase_07 | AC | 390 ms
36,324 KB |
testcase_08 | AC | 395 ms
36,752 KB |
testcase_09 | AC | 441 ms
41,444 KB |
testcase_10 | AC | 393 ms
36,848 KB |
testcase_11 | AC | 400 ms
37,204 KB |
testcase_12 | WA | - |
testcase_13 | AC | 399 ms
36,632 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 395 ms
36,544 KB |
testcase_17 | AC | 441 ms
37,724 KB |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 434 ms
40,336 KB |
testcase_21 | AC | 476 ms
44,268 KB |
testcase_22 | AC | 418 ms
37,112 KB |
testcase_23 | AC | 450 ms
41,780 KB |
testcase_24 | TLE | - |
testcase_25 | TLE | - |
testcase_26 | TLE | - |
testcase_27 | TLE | - |
testcase_28 | TLE | - |
testcase_29 | TLE | - |
testcase_30 | TLE | - |
testcase_31 | AC | 1,381 ms
60,280 KB |
testcase_32 | AC | 1,159 ms
60,072 KB |
testcase_33 | TLE | - |
testcase_34 | TLE | - |
testcase_35 | AC | 590 ms
55,732 KB |
testcase_36 | TLE | - |
testcase_37 | AC | 1,241 ms
60,160 KB |
testcase_38 | TLE | - |
testcase_39 | TLE | - |
testcase_40 | AC | 400 ms
36,588 KB |
testcase_41 | AC | 495 ms
46,392 KB |
testcase_42 | TLE | - |
testcase_43 | AC | 1,723 ms
60,212 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.fsproj を復元しました (277 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) /home/judge/data/code/Main.fs(69,9): warning FS0025: この式のパターン マッチが不完全です たとえば、値 '[|_; _; _|]' はパターンに含まれないケースを示す可能性があります。 [/home/judge/data/code/main.fsproj] main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
module Main let readLine () : int array = stdin.ReadLine().Split([|' '|]) |> Array.map int type matrix = int[,] let reorderColsByColPerm (s : matrix) (x : int) : matrix = let t = Array2D.copy s for r = 1 to Array2D.length1 s do for c = 1 to Array2D.length2 s do let v = Array2D.get s (r-1) (c-1) let cx = Array2D.get s (c-1) (x-1) Array2D.set t (r-1) (cx-1) v t let reorderRowsByRowPerm (s : matrix) (y : int) : matrix = let t = Array2D.copy s for r = 1 to Array2D.length1 s do for c = 1 to Array2D.length2 s do let v = Array2D.get s (r-1) (c-1) let ry = Array2D.get s (y-1) (r-1) Array2D.set t (ry-1) (c-1) v t let rec search (b : matrix) (k : int) (t : matrix) (v : int array) : bool = if k = 0 then b = t else let n = Array2D.length1 b b[0,*] |> Array.toSeq |> Seq.map ((*) 2) |> Seq.append (Array.toSeq b[0,*]) |> Seq.exists (fun op -> Array.set v (Array.length v - k) op let s = Array2D.copy t let w = if op <= n then reorderColsByColPerm s op else reorderRowsByRowPerm s (op-n) search b (k-1) w v ) let cycle (p : int array) : int = let rec f (cnt : int) (t : int array) (w : int array) : int = p |> Array.iteri (fun i e -> Array.set t (e-1) (Array.get w i)) if p = t then cnt else f (cnt+1) w t f 1 (Array.copy p) (Array.copy p) let solve (n : int) (k : int) (a : matrix) (b : matrix) : int array = let ops = Array.zeroCreate k ignore <| search b k a ops let f ((ans, s) : int array * matrix) (op : int) : int array * matrix = let p = if op <= n then s[*,op-1] else s[op-1-n,*] let t = if op <= n then reorderColsByColPerm s op else reorderRowsByRowPerm s (op-n) let cnt = cycle p - 1 let z0 = if op <= n then op else (op-n) let tmp = seq { 1..cnt } |> Seq.scan (fun z _ -> Array.get p (z-1)) z0 |> Seq.tail |> Seq.map (fun z -> if op <= n then z else (z+n)) |> Seq.toArray (Array.append tmp ans, t) ops |> Array.fold f ([||],a) |> fst [<EntryPoint>] let main (_args: string array) : int = let [|n; k|] = readLine() let a = array2D [|for _ in 1..n -> readLine()|] let b = array2D [|for _ in 1..n -> readLine()|] let ans = solve n k a b printfn "%d" (Array.length ans) let f (op : int) : string = if op <= n then (sprintf "C %d" op) else (sprintf "R %d" (op-n)) ans |> Array.map f |> Array.iter (printfn "%s") 0