結果

問題 No.270 next_permutation (1)
ユーザー Min_25Min_25
提出日時 2017-05-05 08:27:03
言語 PyPy2
(7.3.13)
結果
AC  
実行時間 142 ms / 2,000 ms
コード長 3,025 bytes
コンパイル時間 402 ms
コンパイル使用メモリ 77,608 KB
実行使用メモリ 101,120 KB
最終ジャッジ日時 2023-10-12 09:36:32
合計ジャッジ時間 3,418 ms
ジャッジサーバーID
(参考情報)
judge12 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 73 ms
76,592 KB
testcase_01 AC 75 ms
76,288 KB
testcase_02 AC 74 ms
76,248 KB
testcase_03 AC 74 ms
76,080 KB
testcase_04 AC 73 ms
76,288 KB
testcase_05 AC 74 ms
76,472 KB
testcase_06 AC 74 ms
76,104 KB
testcase_07 AC 93 ms
78,856 KB
testcase_08 AC 95 ms
78,960 KB
testcase_09 AC 103 ms
79,544 KB
testcase_10 AC 141 ms
101,120 KB
testcase_11 AC 131 ms
100,184 KB
testcase_12 AC 126 ms
96,788 KB
testcase_13 AC 142 ms
99,888 KB
testcase_14 AC 123 ms
96,176 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys

def solve():
  def count(flv, lv, num, nth):
    q, r = divmod(nth, facts[flv])
    if flv == lv:
      ret = (q > num) * facts[flv]
      if q == num:
        ret += r
    else:
      ret = (q - (q > num)) * facts[flv - 1]
      if q != num:
        ret += count(flv - 1, lv, num - (q < num), r)
    return ret

  def next_permutation(seq):
    N = len(seq)
    for i in range(N - 1, 0, -1):
      if seq[i - 1] < seq[i]:
        j = N - 1
        while seq[j] <= seq[i - 1]:
          j -= 1
        seq[i - 1], seq[j] = seq[j], seq[i - 1]
        seq[i:] = seq[i:][::-1]
        break
    else:
      seq[:] = seq[::-1]
      return False
    return True

  def permutation_rank(n, seq):
    def add(idx, v):
      while idx <= n:
        fenwick[idx] += v
        idx += idx & -idx
      return
    def read(idx):
      ret = 0
      while idx > 0:
        ret += fenwick[idx]
        idx &= idx - 1
      return ret
    if n == 0:
      return 0
    fenwick = [0] * (n + 1)
    for i in range(2, n + 1):
      add(i, 1)
    ret = 0
    for i, c in enumerate(seq):
      ret += read(c + 1) * facts[n - 1 - i]
      add(c + 1, -1)
    return ret

  F = 20
  facts = [1] * (F + 1)
  for i in range(1, F + 1):
    facts[i] = facts[i - 1] * i

  input = sys.stdin.readline
  for line in sys.stdin:
    N, K = map(int, line.split())
    A = [c - 1 for c in map(int, input().split())]
    B = [c - 1 for c in map(int, input().split())]

    def fast_sum(N, K, base, B):
      ret = 0
      for i in range(N):
        for j in range(N):
          ret += abs(B[i] - base[j]) * count(N - 1, N - 1 - i, j, K)
      return ret

    ans = 0
    if N <= F:
      q, K = divmod(K, facts[N])
      s = 0
      for i in range(N):
        for j in range(N):
          s += abs(B[i] - j)
      s *= facts[N - 1]
      ans += q * s
      rank = permutation_rank(N, A)
      base = list(range(N))
      if rank + K > facts[N]:
        ans += s
        ans += fast_sum(N, rank + K - facts[N], base, B)
        ans -= fast_sum(N, rank, base, B)
      else:
        ans += fast_sum(N, rank + K, base, B)
        ans -= fast_sum(N, rank, base, B)
    else:
      last = A[-F:]
      base = sorted(last)
      conv = {l: i for i, l in enumerate(base)}
      rank = permutation_rank(F, [conv[p] for p in last])
      if rank + K > facts[F]:
        s = 0
        for i in range(N - F):
          s += abs(B[i] - A[i])
        ans += s * (facts[F] - rank)
        ans += fast_sum(F, facts[F], base, B[-F:])
        ans -= fast_sum(F, rank, base, B[-F:])
        A = A[:-F] + base[::-1]
        next_permutation(A)
        ans += fast_sum(F, rank + K - facts[F], sorted(A[-F:]), B[-F:])
        s = 0
        for i in range(N - F):
          s += abs(B[i] - A[i])
        ans += s * (rank + K - facts[F])
      else:
        ans += fast_sum(F, rank + K, base, B[-F:])
        ans -= fast_sum(F, rank, base, B[-F:])
        s = 0
        for i in range(N - F):
          s += abs(B[i] - A[i])
        ans += s * K
    print(ans)

solve()
0