結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712ID 21712
提出日時 2024-12-18 00:45:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 238 ms / 2,000 ms
コード長 2,304 bytes
コンパイル時間 348 ms
コンパイル使用メモリ 82,404 KB
実行使用メモリ 78,988 KB
最終ジャッジ日時 2024-12-18 00:45:26
合計ジャッジ時間 7,271 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
55,608 KB
testcase_01 AC 43 ms
61,772 KB
testcase_02 AC 41 ms
54,472 KB
testcase_03 AC 182 ms
78,284 KB
testcase_04 AC 38 ms
54,048 KB
testcase_05 AC 44 ms
61,268 KB
testcase_06 AC 42 ms
53,084 KB
testcase_07 AC 37 ms
53,932 KB
testcase_08 AC 40 ms
54,976 KB
testcase_09 AC 118 ms
77,416 KB
testcase_10 AC 40 ms
54,680 KB
testcase_11 AC 57 ms
69,324 KB
testcase_12 AC 151 ms
78,988 KB
testcase_13 AC 38 ms
54,380 KB
testcase_14 AC 84 ms
77,412 KB
testcase_15 AC 107 ms
77,956 KB
testcase_16 AC 39 ms
53,300 KB
testcase_17 AC 82 ms
76,944 KB
testcase_18 AC 153 ms
78,552 KB
testcase_19 AC 43 ms
60,776 KB
testcase_20 AC 90 ms
76,928 KB
testcase_21 AC 80 ms
76,860 KB
testcase_22 AC 38 ms
53,268 KB
testcase_23 AC 102 ms
76,948 KB
testcase_24 AC 211 ms
78,384 KB
testcase_25 AC 171 ms
78,132 KB
testcase_26 AC 170 ms
77,356 KB
testcase_27 AC 139 ms
78,504 KB
testcase_28 AC 192 ms
78,760 KB
testcase_29 AC 158 ms
77,612 KB
testcase_30 AC 183 ms
78,176 KB
testcase_31 AC 168 ms
77,480 KB
testcase_32 AC 101 ms
77,468 KB
testcase_33 AC 181 ms
77,840 KB
testcase_34 AC 179 ms
77,992 KB
testcase_35 AC 174 ms
78,648 KB
testcase_36 AC 96 ms
77,056 KB
testcase_37 AC 127 ms
77,616 KB
testcase_38 AC 198 ms
77,972 KB
testcase_39 AC 161 ms
78,740 KB
testcase_40 AC 39 ms
53,492 KB
testcase_41 AC 156 ms
77,848 KB
testcase_42 AC 165 ms
77,960 KB
testcase_43 AC 238 ms
77,980 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#  yukicoder - ProblemID 11672 - writer's solution

class PPuzzle:
	def __init__(self, n):
		self.n = n
		self.f = []
		self.iCol = []
		self.iRow = []
	def scan(self):
		self.f = [list(map(int, input().split())) for _ in range(self.n)]
		self.iCol = list(range(self.n))
		self.iRow = list(range(self.n))
		return self
	def at(self, r, c):
		return self.f[self.iRow[r-1]][self.iCol[c-1]]
	def clone(self):
		p = PPuzzle(self.n)
		p.f = self.f
		p.iCol = self.iCol.copy()
		p.iRow = self.iRow.copy()
		return p
	def is_same(self, p):
		for r in range(1,self.n+1):
			for c in range(1,self.n+1):
				if self.at(r,c) != p.at(r,c):
					return False
		return True
	def select_col(self, c):
		return [self.at(r, c) for r in range(1,self.n+1)]
	def select_row(self, r):
		return [self.at(r, c) for c in range(1,self.n+1)]
	def operate_col(self, c):
		s = self.select_col(c)
		tmp = self.iCol.copy()
		for (i,e) in enumerate(s):
			self.iCol[e-1] = tmp[i]
	def operate_row(self, r):
		s = self.select_row(r)
		tmp = self.iRow.copy()
		for (i,e) in enumerate(s):
			self.iRow[e-1] = tmp[i]

class Problem:
	def __init__(self):
		self.N = 0
		self.K = 0
		self.A = None
		self.B = None
	def scan(self):
		self.N, self.K = list(map(int,input().split()))
		self.A = PPuzzle(self.N).scan()
		self.B = PPuzzle(self.N).scan()
		return self

def solve(p):
	def search(k, x, m):
		if k == 0:
			return m if p.B.is_same(x) else None
		for i in range(1,p.N*2+1):
			y = x.clone()
			m.append(i)
			if i <= p.N:
				y.operate_col(i)
			else:
				y.operate_row(i-p.N)
			if search(k-1,y,m):
				return m
			m.pop()
		return None
	m = search(p.K, p.A, [])
	z = p.A.clone()
	ps = []
	for i in m:
		s = z.select_col(i) if i <= p.N else z.select_row(i-p.N)
		ps.append((i,s))
		if i <= p.N:
			z.operate_col(i)
		else:
			z.operate_row(i-p.N)
	def cycle(s):
		c = 0
		x = s.copy()
		while True:
			c += 1
			y = x.copy()
			for (i,e) in enumerate(s):
				x[e-1] = y[i]
			if x == s:
				return c
	ps.reverse()
	ans = []
	for (i,s) in ps:
		c = cycle(s)
		g = 0 if i <= p.N else p.N
		h = s[i-1-g]
		for _ in range(c-1):
			ans.append(h+g)
			h = s[h-1]
	return ans
			

if __name__ == '__main__':
	p = Problem().scan()
	ans = solve(p)
	print(len(ans))
	for x in ans:
		if x <= p.N:
			print("C", x)
		else:
			print("R", x-p.N)
0