結果

問題 No.270 next_permutation (1)
コンテスト
ユーザー Min_25
提出日時 2017-05-05 08:27:03
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 146 ms / 2,000 ms
コード長 3,025 bytes
コンパイル時間 1,651 ms
コンパイル使用メモリ 76,580 KB
実行使用メモリ 98,368 KB
最終ジャッジ日時 2024-09-14 08:32:52
合計ジャッジ時間 4,565 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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