結果

問題 No.2986 Permutation Puzzle
コンテスト
ユーザー ID 21712
提出日時 2024-12-25 22:20:41
言語 Julia
(2.11.2)
結果
AC  
実行時間 1,292 ms / 2,000 ms
コード長 1,686 bytes
コンパイル時間 117 ms
コンパイル使用メモリ 6,948 KB
実行使用メモリ 320,712 KB
最終ジャッジ日時 2024-12-25 22:21:51
合計ジャッジ時間 53,326 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

const Mat = Vector{Vector{Int}}

function reorderColsByColPerm(s::Matrix, x::Int)
	t = deepcopy(s)
	for r = 1:size(t,1), c = 1:size(t,1)
		s[ r , t[c,x] ] = t[r,c]
	end
end

function reorderRowsByRowPerm(s::Matrix, y::Int)
	t = deepcopy(s)
	for r = 1:size(t,1), c = 1:size(t,1)
		s[ t[y,r] , c ] = t[r,c]
	end
end

function search(b::Matrix, k::Int, t::Matrix, v::Vector{Int})::Bool
	if k == 0
		return b == t
	end
	n = size(t,1)
	for i = 1:n*2
		v[k] = i
		s = deepcopy(t)
		if i <= n
			reorderColsByColPerm(s, i)
		else
			reorderRowsByRowPerm(s, i-n)
		end
		if search(b, k-1, s, v)
			return true
		end
	end
	false
end

function cycle(p::AbstractVector{Int})::Int
	w = copy(p)
	t = copy(p)
	cnt = 0
	while true
		cnt += 1
		for i = 1:length(p)
			t[p[i]] = w[i]
		end
		if t == p
			return cnt
		end
		w = copy(t)
	end
end

function solve(n::Int, k::Int, a::Matrix, b::Matrix)::Vector{Int}
	ops = Vector{Int}(undef,k)
	search(b, k, a, ops)
	ans = Int[]
	for op in reverse(ops)
		p = op <= n ? selectdim(a,2,op) : selectdim(a,1,op-n)
		z = op <= n ? op : (op-n)
		cnt = cycle(p) - 1
		tmp = Vector{Int}(undef,cnt)
		for i in 1:cnt
			z = p[z]
			tmp[i] = op <= n ? z : (z+n)
		end
		ans = vcat(tmp, ans)
		if op <= n
			reorderColsByColPerm(a, op)
		else
			reorderRowsByRowPerm(a, op-n)
		end
	end
	ans
end

function main()
	readInts() = map(s -> parse(Int, s), split(readline(), " "))
	toMatrix(m) = reduce(vcat, transpose(m))
	
	n, k = readInts()
	a = toMatrix([readInts() for _ in 1:n])
	b = toMatrix([readInts() for _ in 1:n])
	ans = solve(n, k, a, b)
	println(length(ans))
	for op in ans
		if op <= n
			println("C $op")
		else
			println("R $(op-n)")
		end
	end
end


main()
0