#1059514 (PyPy3) No.270 next_permutation (1)

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX