結果

問題 No.775 tatyamと素数大富豪(hard)
ユーザー qwewe
提出日時 2025-05-14 12:53:58
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,039 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 82,408 KB
実行使用メモリ 821,360 KB
最終ジャッジ日時 2025-05-14 12:55:30
合計ジャッジ時間 5,708 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4 WA * 1
other AC * 2 WA * 2 MLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import heapq
from functools import cmp_to_key

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    K = int(input[1])
    cards = input[2:2+N]
    
    # Custom comparator to sort cards for maximum concatenated value
    def compare(a, b):
        if a + b > b + a:
            return -1
        else:
            return 1
    
    # Sort the cards based on the custom comparator
    cards_sorted = sorted(cards, key=cmp_to_key(compare))
    initial_tuple = tuple(cards_sorted)
    initial_str = ''.join(initial_tuple)
    
    # Max-heap using a custom class to reverse comparison
    heap = []
    visited = set()
    heapq.heappush(heap, Element(initial_str, initial_tuple))
    visited.add(initial_tuple)
    
    result = []
    for _ in range(K):
        element = heapq.heappop(heap)
        current_str = element.s
        current_tuple = element.t
        result.append(current_str)
        
        # Generate all possible next candidates by swapping each pair
        current_list = list(current_tuple)
        n = len(current_list)
        for i in range(n):
            for j in range(i + 1, n):
                if current_list[i] == current_list[j]:
                    continue  # Skip if same value to avoid duplicates
                # Swap to create a new candidate
                new_list = current_list.copy()
                new_list[i], new_list[j] = new_list[j], new_list[i]
                new_tuple = tuple(new_list)
                if new_tuple not in visited:
                    new_str = ''.join(new_tuple)
                    heapq.heappush(heap, Element(new_str, new_tuple))
                    visited.add(new_tuple)
    
    for s in result:
        print(s)

# Helper class to reverse the comparison for max-heap
class Element:
    def __init__(self, s, t):
        self.s = s
        self.t = t  # tuple representation of the card list
    def __lt__(self, other):
        return self.s > other.s  # Reverse comparison for max-heap

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