結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2025-01-17 02:02:30
言語 OCaml
(5.2.1)
結果
AC  
実行時間 242 ms / 2,000 ms
コード長 2,215 bytes
コンパイル時間 1,804 ms
コンパイル使用メモリ 22,656 KB
実行使用メモリ 6,016 KB
最終ジャッジ日時 2025-01-17 02:02:38
合計ジャッジ時間 5,974 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
File "Main.ml", line 77, characters 5-16:
77 | 	let [| n ; k |] = read_ints () in
     	    ^^^^^^^^^^^
Warning 8 [partial-match]: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
[|  |]

ソースコード

diff # 

type matrix = int array array;;

let reorder_cols_by_col_perm (s : matrix) (x : int) : unit =
	let t = Array.map Array.copy s in
	t |> Array.iteri (fun r ->
		Array.iteri (fun c e ->
			s.( r ).( t.(c).(x) ) <- e
		)
	);;

let reorder_rows_by_row_perm (s : matrix) (y : int) : unit =
	let t = Array.map Array.copy s in
	t |> Array.iteri (fun r ->
		Array.iteri (fun c e ->
			s.( t.(y).(r) ).( c ) <- e
		)
	);;

let rec search (n : int) (b : matrix) (k : int) (t : matrix) : int list option =
	match k with
	| 0 -> if b = t then Some [] else None
	| _ ->
		Seq.init (2*n) Fun.id
		|> Seq.find_map (fun op ->
			let s = Array.map Array.copy t in
			let () = if op < n
				then reorder_cols_by_col_perm s op
				else reorder_rows_by_row_perm s (op-n) in
			search n b (k-1) s
			|> Option.map (List.cons op)
		);;

let select_col (s : matrix) (x : int) : int array =
	Array.map (Fun.flip Array.get x) s;;

let select_row (s : matrix) (y : int) : int array =
	Array.copy s.(y);;
	
let cycle_size (p : int array) : int =
	let rec f cnt w =
		let t = Array.copy w in
		let () = Array.iteri (fun i e -> t.(e) <- w.(i)) p in
		if t = p
			then cnt
			else f (cnt+1) t in f 1 p;;

let solve (n : int) (k : int) (a : matrix) (b : matrix) : int list =
	search n b k a
	|> Option.get
	|> List.map (fun op ->
		let p = if op < n
			then select_col a op
			else select_row a (op-n) in
		let () = if op < n
			then reorder_cols_by_col_perm a op
			else reorder_rows_by_row_perm a (op-n) in
		let cnt = cycle_size p - 1 in
		Seq.iterate (Array.get p) (op mod n)
		|> Seq.map (fun v -> v + op / n * n)
		|> Seq.drop 1
		|> Seq.take cnt
		|> List.of_seq
	)
	|> List.rev
	|> List.flatten;;

let read_ints () : int array =
	read_line ()
	|> String.split_on_char ' '
	|> List.map int_of_string
	|> Array.of_list;;

let read_matrix (n : int) : matrix =
	Array.init n @@ fun _ -> read_ints () |> Array.map pred;;

let main () : unit =
	let [| n ; k |] = read_ints () in
	let a = read_matrix n in
	let b = read_matrix n in
	let ans = solve n k a b in
	Printf.printf "%d\n" (List.length ans);
	ans
	|> List.iter (fun op ->
		if op < n
			then Printf.printf "C %d\n" (op+1)
			else Printf.printf "R %d\n" (op+1-n)
	);
	exit 0;;

main ();;
0