結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2025-01-12 03:00:46
言語 Elixir
(1.18.1)
結果
AC  
実行時間 800 ms / 2,000 ms
コード長 2,138 bytes
コンパイル時間 1,029 ms
コンパイル使用メモリ 80,864 KB
実行使用メモリ 67,596 KB
最終ジャッジ日時 2025-01-12 03:01:38
合計ジャッジ時間 30,427 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #

defmodule Main do

	defp is_same(n,b,a,irow,icol) do
		Enum.all? 0..n-1, fn r ->
			y = elem irow, r
			Enum.all? 0..n-1, fn c ->
				x = elem icol, c
				elem((elem b, r), c) === elem((elem a, y), x)
			end
		end
	end
	
	defp select_col(n,a,irow,icol,x) do
		c = elem icol, x
		0..n-1
		|> Enum.map(& (elem irow, &1))
		|> Enum.map(fn r -> elem((elem a, r), c) end)
	end
	
	defp select_row(n,a,irow,icol,y) do
		r = elem irow, y
		0..n-1
		|> Enum.map(& (elem icol, &1))
		|> Enum.map(fn c -> elem((elem a, r), c) end)
	end
	
	defp rotate(ix, p) do
		Enum.with_index(p)
		|> Enum.reduce(ix, fn {e,i}, acc ->
				put_elem acc, e, (elem ix, i)
			end)
	end

	defp search(n,b,k,a,irow,icol) do
		if k === 0 do
			if is_same(n, b, a, irow, icol), do: [], else: nil
		else
			Enum.find_value 0..2*n-1, fn op ->
				{p,irow2,icol2} = if op < n do
					p = select_col n,a,irow,icol,op
					{p, irow, rotate(icol,p)}
				else
					p = select_row n,a,irow,icol,op-n
					{p, rotate(irow,p), icol}
				end
				case search n,b,k-1,a,irow2,icol2 do
					ops when is_list(ops) -> [ {p,op} | ops ]
					_ -> nil
				end
			end
		end
	end
	
	defp cycle(p) do
		pp = List.to_tuple p
		f = fn f, w, c -> 
			case w do
				^pp -> c
				_ -> f.(f, rotate(w,p), c+1)
			end
		end
		f.(f, rotate(pp, p), 1)
	end

	defp solve(n,k,a,b) do
		ix = Range.to_list(0..n-1) |> List.to_tuple
		search(n,b,k,a,ix,ix)
		|> Enum.map(fn {p,op} ->
				pp = List.to_tuple p
				z = Integer.mod(op,n)
				cnt = cycle(p) - 1
				1..cnt
				|> Enum.scan(z, fn _,z -> (elem pp, z) end)
				|> Enum.map(& (&1 + div(op,n)*n))
			end)
		|> Enum.reverse()
		|> Enum.concat()
	end

	defp read_ints() do
		IO.gets("")
		|> String.split()
		|> Enum.map(&String.to_integer/1)
	end
	
	defp read_matrix(n) do
		1 .. n
		|> Enum.map(fn _ ->
				read_ints()
				|> Enum.map(& &1-1)
				|> List.to_tuple
			end)
		|> List.to_tuple
	end

	def main() do
		[n, k] = read_ints()
		a = read_matrix n
		b = read_matrix n
		
		ans = solve n, k, a, b
		
		IO.puts("#{length ans}")
		for op <- ans do
			if op < n do
				IO.puts("C #{op+1}")
			else
				IO.puts("R #{op+1-n}")
			end
		end
	end
end
0