結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
6,144 KB
testcase_01 AC 11 ms
6,144 KB
testcase_02 AC 11 ms
6,144 KB
testcase_03 AC 12 ms
6,144 KB
testcase_04 AC 12 ms
6,144 KB
testcase_05 AC 11 ms
6,016 KB
testcase_06 AC 12 ms
6,016 KB
testcase_07 AC 14 ms
6,016 KB
testcase_08 AC 15 ms
6,400 KB
testcase_09 AC 25 ms
7,492 KB
testcase_10 AC 131 ms
18,704 KB
testcase_11 AC 130 ms
18,576 KB
testcase_12 AC 130 ms
18,444 KB
testcase_13 AC 125 ms
17,548 KB
testcase_14 AC 125 ms
17,764 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
  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 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