結果

問題 No.270 next_permutation (1)
ユーザー Min_25Min_25
提出日時 2017-05-05 12:05:40
言語 Python2
(2.7.18)
結果
AC  
実行時間 131 ms / 2,000 ms
コード長 3,449 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 7,168 KB
実行使用メモリ 18,700 KB
最終ジャッジ日時 2024-09-14 08:40:46
合計ジャッジ時間 1,736 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
6,812 KB
testcase_01 AC 11 ms
6,816 KB
testcase_02 AC 11 ms
6,944 KB
testcase_03 AC 11 ms
6,940 KB
testcase_04 AC 11 ms
6,940 KB
testcase_05 AC 11 ms
6,944 KB
testcase_06 AC 11 ms
6,940 KB
testcase_07 AC 11 ms
6,940 KB
testcase_08 AC 12 ms
6,944 KB
testcase_09 AC 23 ms
7,364 KB
testcase_10 AC 125 ms
18,572 KB
testcase_11 AC 131 ms
18,660 KB
testcase_12 AC 126 ms
18,700 KB
testcase_13 AC 124 ms
17,800 KB
testcase_14 AC 122 ms
17,640 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 counts(n, target, nth):
    counts = [0] * n
    cnt = 0
    for i in range(n - 1, -1, -1):
      q, nth = divmod(nth, facts[i])
      counts[i] = cnt + (q > target) * facts[i] + (q == target) * nth
      cnt += (q - (q > target)) * facts[i - 1]
      if q == target:
        for j in range(i - 1, -1, -1):
          counts[j] = cnt
        break
      target -= (q < target)
    return counts[::-1]

  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
  while 1:
    try:
      N, K = map(int, input().split())
    except:
      break
    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 j in range(N):
        for i, c in enumerate(counts(N, j, K)):
          ret += abs(B[i] - base[j]) * c
      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