結果

問題 No.270 next_permutation (1)
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:48:05
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,042 bytes
コンパイル時間 314 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 677,052 KB
最終ジャッジ日時 2025-03-26 15:49:24
合計ジャッジ時間 4,428 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 MLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    K = int(input[ptr])
    ptr += 1
    p = list(map(int, input[ptr:ptr+N]))
    ptr += N
    B = list(map(int, input[ptr:ptr+N]))
    ptr += N

    if K == 0:
        print(0)
        return

    def initial_distance(p, B):
        return sum(abs(a - b) for a, b in zip(p, B))

    total = initial_distance(p, B)
    if K == 1:
        print(total)
        return

    if N <= 12:
        # Find cycle
        from collections import OrderedDict
        seen = OrderedDict()
        current = p.copy()
        cycle = []
        key = tuple(current)
        while key not in seen:
            seen[key] = len(cycle)
            cycle.append(current.copy())
            # Generate next permutation
            i = N-2
            while i >=0 and current[i] >= current[i+1]:
                i -= 1
            if i == -1:
                current = current[::-1]
            else:
                j = N-1
                while current[j] <= current[i]:
                    j -= 1
                current[i], current[j] = current[j], current[i]
                left = i+1
                right = N-1
                while left < right:
                    current[left], current[right] = current[right], current[left]
                    left +=1
                    right -=1
            key = tuple(current)
        # Find where the cycle starts
        start_idx = seen[key]
        cycle = cycle[start_idx:]
        # Precompute distances
        cycle_distances = [initial_distance(perm, B) for perm in cycle]
        cycle_length = len(cycle)
        # Compute total
        if K <= start_idx:
            # All steps are before the cycle
            print(sum(initial_distance(perm, B) for perm in seen.keys()[:K]))
        else:
            sum_before_cycle = sum(initial_distance(perm, B) for perm in list(seen.keys())[:start_idx])
            K -= start_idx
            full_cycles = K // cycle_length
            remainder = K % cycle_length
            sum_cycle = sum(cycle_distances)
            total = sum_before_cycle + full_cycles * sum_cycle + sum(cycle_distances[:remainder])
            print(total)
        return
    else:
        current = p.copy()
        current_sum = initial_distance(current, B)
        total_sum = current_sum
        for _ in range(K-1):
            # Generate next permutation
            i = N-2
            while i >= 0 and current[i] >= current[i+1]:
                i -= 1
            if i == -1:
                # Wrap around, all elements change
                old = current.copy()
                current = current[::-1]
                # Update current_sum
                new_sum = initial_distance(current, B)
                total_sum += new_sum
                current_sum = new_sum
            else:
                # Find j
                j = N-1
                while current[j] <= current[i]:
                    j -= 1
                # Swap i and j
                # Update current_sum
                current_sum -= abs(current[i] - B[i])
                current_sum -= abs(current[j] - B[j])
                current[i], current[j] = current[j], current[i]
                current_sum += abs(current[i] - B[i])
                current_sum += abs(current[j] - B[j])
                # Reverse from i+1 to end
                left = i+1
                right = N-1
                while left < right:
                    # Swap left and right
                    current_sum -= abs(current[left] - B[left])
                    current_sum -= abs(current[right] - B[right])
                    current[left], current[right] = current[right], current[left]
                    current_sum += abs(current[left] - B[left])
                    current_sum += abs(current[right] - B[right])
                    left += 1
                    right -= 1
                total_sum += current_sum
        print(total_sum)
        return

if __name__ == "__main__":
    main()
0