結果

問題 No.2986 Permutation Puzzle
コンテスト
ユーザー ID 21712
提出日時 2024-12-24 23:05:34
言語 Swift
(6.0.3)
結果
AC  
実行時間 276 ms / 2,000 ms
コード長 2,020 bytes
コンパイル時間 5,192 ms
コンパイル使用メモリ 131,888 KB
実行使用メモリ 9,472 KB
最終ジャッジ日時 2024-12-24 23:05:45
合計ジャッジ時間 6,380 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

func reorderColsByColPerm(_ s: inout [[Int]], _ x: Int) {
	let t = s
	for r in 0..<t.count {
		for c in 0..<t.count {
			s[ r ][ t[c][x]-1 ] = t[r][c]
		}
	}
}

func reorderRowsByRowPerm(_ s: inout [[Int]], _ y: Int) {
	let t = s
	for r in 0..<t.count {
		for c in 0..<t.count {
			s[ t[y][r]-1 ][ c ] = t[r][c]
		}
	}
}

func selectCol(_ s: [[Int]], _ x: Int) -> [Int] {
	s.map { row in row[x] }
}

func selectRow(_ s: [[Int]], _ y: Int) -> [Int] {
	s[y]
}

func solve(_ n: Int, _ k: Int, _ a: [[Int]], _ b: [[Int]]) -> [Int] {
	var ops: [Int] = .init(repeating: 0, count: k)
	_ = search(b, k, a, &ops)
	var ans: [Int] = []
	var s = a
	for op in ops {
		let p = if op < n {
			selectCol(s, op)
		} else {
			selectRow(s, op-n)
		}
		if op < n {
			reorderColsByColPerm(&s, op)
		} else {
			reorderRowsByRowPerm(&s, op-n)
		}
		var tmp: [Int] = []
		var z = op % n
		for _ in 1..<cycle(p) {
			z = p[z]-1
			if op < n {
				tmp.append(z)
			} else {
				tmp.append(z+n)
			}
		}
		ans.insert(contentsOf: tmp, at: 0)
	}
	return ans
}

func search(_ b: [[Int]], _ k: Int, _ t: [[Int]], _ v: inout [Int]) -> Bool {
	if k == 0 {
		return b == t
	}
	for i in 0..<b.count*2 {
		v[v.count-k] = i
		var s = t
		if i < b.count {
			reorderColsByColPerm(&s, i)
		} else {
			reorderRowsByRowPerm(&s, i-b.count)
		}
		if search(b, k-1, s, &v) {
			return true
		}
	}
	return false
}

func cycle(_ p: [Int]) -> Int {
	var t = p
	var w = p
	for cnt in 1... {
		for (i, e) in p.enumerated() {
			t[e-1] = w[i]
		}
		if p == t {
			return cnt
		}
		w = t
	}
	return 0
}

func readInts() -> [Int] {
	readLine()!.split(separator: " ").map { s in  Int(s)! }
}

func main() {
	var firstLine = readInts().makeIterator()
	let n: Int = firstLine.next()!
	let k: Int = firstLine.next()!
	let a: [[Int]] = (1...n).map { _ in readInts() }
	let b: [[Int]] = (1...n).map { _ in readInts() }
	
	let ans = solve(n, k, a, b)
	
	print(ans.count)
	for op in ans {
		if op < n {
			print("C \(op+1)")
		} else {
			print("R \(op+1-n)")
		}
	}
}

main()
0