結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712ID 21712
提出日時 2024-11-29 14:08:06
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 635 ms / 2,000 ms
コード長 2,305 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 11,136 KB
最終ジャッジ日時 2024-12-02 12:32:17
合計ジャッジ時間 10,199 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
11,008 KB
testcase_01 AC 30 ms
11,008 KB
testcase_02 AC 27 ms
11,136 KB
testcase_03 AC 498 ms
11,008 KB
testcase_04 AC 29 ms
11,008 KB
testcase_05 AC 28 ms
11,008 KB
testcase_06 AC 27 ms
11,136 KB
testcase_07 AC 28 ms
11,008 KB
testcase_08 AC 29 ms
11,008 KB
testcase_09 AC 46 ms
11,008 KB
testcase_10 AC 29 ms
11,008 KB
testcase_11 AC 28 ms
11,008 KB
testcase_12 AC 87 ms
11,008 KB
testcase_13 AC 27 ms
11,008 KB
testcase_14 AC 32 ms
11,008 KB
testcase_15 AC 54 ms
11,136 KB
testcase_16 AC 29 ms
11,008 KB
testcase_17 AC 32 ms
11,136 KB
testcase_18 AC 155 ms
11,008 KB
testcase_19 AC 28 ms
11,008 KB
testcase_20 AC 44 ms
11,008 KB
testcase_21 AC 33 ms
11,008 KB
testcase_22 AC 28 ms
11,136 KB
testcase_23 AC 52 ms
11,136 KB
testcase_24 AC 627 ms
10,880 KB
testcase_25 AC 383 ms
11,008 KB
testcase_26 AC 391 ms
11,008 KB
testcase_27 AC 105 ms
11,008 KB
testcase_28 AC 471 ms
11,008 KB
testcase_29 AC 201 ms
11,008 KB
testcase_30 AC 490 ms
11,008 KB
testcase_31 AC 389 ms
11,008 KB
testcase_32 AC 55 ms
10,880 KB
testcase_33 AC 444 ms
11,008 KB
testcase_34 AC 385 ms
11,008 KB
testcase_35 AC 317 ms
11,008 KB
testcase_36 AC 44 ms
11,008 KB
testcase_37 AC 89 ms
10,880 KB
testcase_38 AC 480 ms
11,136 KB
testcase_39 AC 221 ms
11,136 KB
testcase_40 AC 29 ms
11,008 KB
testcase_41 AC 312 ms
11,008 KB
testcase_42 AC 350 ms
11,008 KB
testcase_43 AC 635 ms
11,136 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