結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712
提出日時 2024-12-20 17:21:01
言語 Ruby
(3.4.1)
結果
AC  
実行時間 1,252 ms / 2,000 ms
コード長 1,801 bytes
コンパイル時間 704 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 12,928 KB
最終ジャッジ日時 2024-12-20 17:21:28
合計ジャッジ時間 25,359 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
外部呼び出し有り
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
プレゼンテーションモードにする

if ARGV.size == 0
    system("ruby -W0 --jit -- %s run"%$0)
    exit
end
ARGV.pop
class PPuzzle
    attr_reader :n
    def initialize(n,icol=[],irow=[],matrix=[])
        @n = n
        @icol = icol
        @irow = irow
        @matrix = matrix
    end
    def read()
        @icol = @n.times.to_a
        @irow = @n.times.to_a
        @matrix = @n.times.map{gets.chomp.split.map{|s|s.to_i-1}}
        self
    end
    def clone()
        PPuzzle.new(@n,@icol.dup,@irow.dup,@matrix)
    end
    def at(r,c)
        @matrix[@irow[r]][@icol[c]]
    end
    def select_col(x)
        @n.times.map{|r|self.at(r,x)}
    end
    def select_row(y)
        @n.times.map{|c|self.at(y,c)}
    end
    def operate_col(x)
        pa = self.select_col(x)
        t = @icol.dup
        @n.times{|i| @icol[pa[i]] = t[i] }
    end
    def operate_row(y)
        pa = self.select_row(y)
        t = @irow.dup
        @n.times{|i| @irow[pa[i]] = t[i] }
    end
    def ==(other)
        @n.times.all?{|r| @n.times.all?{|c| self.at(r,c)==other.at(r,c) }}
    end
end
def search(b,k,t,v)
    return t==b if k==0
    for i in t.select_col(0)
        v.push(i)
        s = t.clone
        s.operate_col(i)
        return true if search(b,k-1,s,v)
        v.pop
        v.push(i+b.n)
        s = t.clone
        s.operate_row(i)
        return true if search(b,k-1,s,v)
        v.pop
    end
    false
end
def cycle(p)
    t=[0]*p.size
    w=p.dup
    loop.with_index(1) {|_,cnt|
        p.size.times{|i| t[p[i]] = w[i] }
        break cnt if t == p
        t,w = [w,t]
    }
end
def solve(n,k,a,b)
    ops = []
    search(b,k,a,ops)
    s=a.clone
    ans = []
    ops.each{|op|
        if op<n
            pa = s.select_col(op)
            s.operate_col(op)
        else
            pa = s.select_row(op-n)
            s.operate_row(op-n)
        end
        z = op % n
        tmp = []
        cycle(pa).pred.times {
            z = pa[z]
            tmp.push(op<n ? z : (z+n))
        }
        ans = tmp+ans
    }
    ans
end
n, k = gets.chomp.split.map{|s|s.to_i}
a = PPuzzle.new(n).read()
b = PPuzzle.new(n).read()
ans = solve(n,k,a,b)
puts ans.size
puts ans.map{|op| op<n ? "C %d"%(op+1) : "R %d"%(op+1-n) }*"\n"
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0