結果

問題 No.1311 Reverse Permutation Index
ユーザー yuruhiyayuruhiya
提出日時 2020-12-13 12:13:20
言語 Crystal
(1.11.2)
結果
AC  
実行時間 2 ms / 1,500 ms
コード長 745 bytes
コンパイル時間 11,336 ms
コンパイル使用メモリ 296,892 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-30 21:50:17
合計ジャッジ時間 12,044 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 2 ms
6,812 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

lib C
  fun strtoll(s : UInt8*, p : UInt8**, b : Int32) : Int64
end

class String
  def to_i64
    C.strtoll(self, nil, 10)
  end
end

def index_to_perm(n, x)
  remain = (1..n).to_a
  (1..n).map { |i|
    f = (1..n - i).reduce(1i64) { |acc, i| acc*i }
    i = x // f
    x -= i * f
    remain.delete_at(i)
  }
end

def reverse_perm(n, a)
  index = [-1] * n
  (0...n).each do |i|
    index[a[i] - 1] = i + 1
  end
  index
end

def perm_to_index(n, a)
  remain = (1..n).to_a
  (1..n).sum { |i|
    f = (1..n - i).reduce(1i64) { |acc, i| acc*i }
    i = remain.index(a[i - 1]).not_nil!
    remain.delete_at(i)
    f * i
  }
end

x, n = read_line.split.map(&.to_i64)
a = index_to_perm(n, x)
b = reverse_perm(n, a)
ans = perm_to_index(n, b)
puts ans
0