結果

問題 No.2986 Permutation Puzzle
コンテスト
ユーザー ID 21712
提出日時 2025-01-01 00:15:53
言語 Nim
(2.2.0)
結果
AC  
実行時間 297 ms / 2,000 ms
コード長 1,805 bytes
コンパイル時間 4,461 ms
コンパイル使用メモリ 70,024 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-01-01 00:16:02
合計ジャッジ時間 9,578 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import strutils, sequtils, sugar

type
  Matrix = seq[seq[int]]

proc reorderColsByColPerm(s: var Matrix, x: int) =
  let t = s.dup
  for r in 0 ..< t.len:
    for c in 0 ..< t.len:
      s[ r ][ t[c][x] ] = t[r][c]

proc reorderRowsByRowPerm(s: var Matrix, y: int) =
  let t = s.dup
  for r in 0 ..< t.len:
    for c in 0 ..< t.len:
      s[ t[y][r] ][ c ] = t[r][c]

proc selectCol(s: Matrix, x: int): seq[int] = s.map(row => row[x])

proc selectRow(s: Matrix, y: int): seq[int] = s[y].dup

proc search(b: Matrix, k: int, t: Matrix, ops: var seq[int]): bool =
  if k == 0:
    return t == b
  for op in 0 ..< b.len*2:
    ops[ops.len-k] = op
    var s = t
    if op < b.len:
      s.reorderColsByColPerm(op)
    else:
      s.reorderRowsByRowPerm(op-b.len)
    if search(b, k-1, s, ops):
      return true
  return false

proc solve(n: int, k: int, a: Matrix, b: Matrix): seq[int] =
  var ops = toSeq( 0 ..< k )
  discard search(b, k, a, ops)
  var ans: seq[int] = @[]
  var s = a
  for op in ops:
    let p = if op < n: s.selectCol(op) else: s.selectRow(op-n)
    var t = toSeq(0 ..< n)
    var w = p.dup
    var z = op mod n
    var tmp: seq[int] = @[]
    while true:
      for i in 0 ..< n:
        t[p[i]] = w[i]
      if t == p:
        break
      z = p[z]
      tmp.add(if op < n: z else: (z+n))
      w = t.dup
    ans.insert(tmp, 0)
    if op < n:
      s.reorderColsByColPerm(op)
    else:
      s.reorderRowsByRowPerm(op-n)
  return ans

proc readInts(): seq[int] =
  return stdin.readLine.strip.split.map(parseInt)

let
  nk = readInts()
  n = nk[0]
  k = nk[1]
  a = toSeq(0 ..< n).mapIt(readInts().mapIt(it-1))
  b = toSeq(0 ..< n).mapIt(readInts().mapIt(it-1))
  ans = solve(n, k, a, b)

echo ans.len
for op in ans:
  if op < n:
    echo "C " & $(op+1)
  else:
    echo "R " & $(op+1-n)
0