結果

問題 No.270 next_permutation (1)
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:21:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 144 ms / 2,000 ms
コード長 2,068 bytes
コンパイル時間 188 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 117,192 KB
最終ジャッジ日時 2025-03-31 17:22:23
合計ジャッジ時間 2,490 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    
    N = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    
    if K == 0:
        print(0)
        return
    
    p = list(map(int, data[idx:idx+N]))
    idx += N
    B = list(map(int, data[idx:idx+N]))
    
    current = p.copy()
    sum_dist = 0
    for i in range(N):
        sum_dist += abs(current[i] - B[i])
    
    total = sum_dist
    remaining = K - 1
    
    while remaining > 0:
        # Find the largest i such that current[i] < current[i+1]
        i = N - 2
        while i >= 0 and current[i] >= current[i+1]:
            i -= 1
        
        if i == -1:
            # current is the last permutation, wrap around to the first
            for j in range(N):
                sum_dist -= abs(current[j] - B[j])
                current[j] = j + 1
                sum_dist += abs(current[j] - B[j])
            total += sum_dist
            remaining -= 1
            continue
        
        # Find the largest j > i such that current[j] > current[i]
        j = N - 1
        while current[j] <= current[i]:
            j -= 1
        
        # Swap current[i] and current[j]
        sum_dist -= abs(current[i] - B[i])
        sum_dist -= abs(current[j] - B[j])
        current[i], current[j] = current[j], current[i]
        sum_dist += abs(current[i] - B[i])
        sum_dist += abs(current[j] - B[j])
        
        # Reverse current[i+1:]
        # Calculate the old contribution and update sum_dist
        left = i + 1
        right = N - 1
        while left < right:
            sum_dist -= abs(current[left] - B[left])
            sum_dist -= abs(current[right] - B[right])
            current[left], current[right] = current[right], current[left]
            sum_dist += abs(current[left] - B[left])
            sum_dist += abs(current[right] - B[right])
            left += 1
            right -= 1
        
        total += sum_dist
        remaining -= 1
    
    print(total)

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