結果

問題 No.2986 Permutation Puzzle
コンテスト
ユーザー ID 21712
提出日時 2025-01-13 23:35:51
言語 Crystal
(1.14.0)
結果
AC  
実行時間 310 ms / 2,000 ms
コード長 1,714 bytes
コンパイル時間 14,703 ms
コンパイル使用メモリ 314,412 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-01-13 23:36:19
合計ジャッジ時間 21,153 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

alias Matrix = Array(Array(Int32))

def reorder_cols_by_col_perm(s : Matrix, x : Int32)
	t = s.clone
	t.each_index do |r|
		t.each_index do |c|
			s[ r ][ t[c][x] ] = t[r][c]
		end
	end
end

def reorder_rows_by_row_perm(s : Matrix, y : Int32)
	t = s.clone
	t.each_index do |r|
		t.each_index do |c|
			s[ t[y][r] ][ c ] = t[r][c]
		end
	end
end

def search(n : Int32, b : Matrix, k : Int32, t : Matrix, ops : Array(Int32)) : Bool
	return b == t if k == 0
	(0...n*2).each do |op|
		ops[-k] = op
		s = t.clone
		if op < n
			reorder_cols_by_col_perm(s, op)
		else
			reorder_rows_by_row_perm(s, op-n)
		end
		return true if search(n, b, k-1, s, ops)
	end
	false
end

def select_col(s : Matrix, x : Int32) : Array(Int32)
	s.map &.[x]
end

def select_row(s : Matrix, y : Int32) : Array(Int32)
	s[y].dup
end

def cycle_size(perm : Array(Int32)) : Int32
	t = Array.new(perm.size, 0)
	w = perm.dup
	(1..).each do |cnt|
		perm.each_with_index do |e, i|
			t[e] = w[i]
		end
		return cnt if perm == t
		w.replace t
	end
end

def solve(n : Int32, k : Int32, a : Matrix, b : Matrix) : Array(Int32)
	ops = Array.new(k, 0)
	search(n, b, k, a, ops)
	ops.map{ |op|
		if op < n
			perm = select_col(a, op)
			reorder_cols_by_col_perm(a, op)
		else
			perm = select_row(a, op-n)
			reorder_rows_by_row_perm(a, op-n)
		end
		z = op % n
		cycle_size(perm).pred.times.map{
			z = perm[z % n] + (op // n)*n
		}.to_a
	}.reverse.flatten
end

def read_ints : Array(Int32)
	gets.not_nil!.split.map &.to_i
end

n,k = read_ints
a = n.times.map{ read_ints.map &.pred }.to_a
b = n.times.map{ read_ints.map &.pred }.to_a

ans = solve(n, k, a, b)

puts ans.size
ans.each do |op|
	if op < n
		puts "C #{op+1}"
	else
		puts "R #{op+1-n}"
	end
end
0