結果
問題 |
No.2986 Permutation Puzzle
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()