結果

問題 No.1630 Sorting Integers (Greater than K)
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:28:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,973 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,520 KB
実行使用メモリ 147,360 KB
最終ジャッジ日時 2025-03-20 20:29:39
合計ジャッジ時間 3,255 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 15 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    N, K = sys.stdin.readline().split()
    N = int(N)
    K_digits = list(K)
    len_K = len(K_digits)
    c = list(map(int, sys.stdin.readline().split()))
    counts = [0] * 10  # counts[1..9]
    for i in range(9):
        counts[i+1] = c[i]

    # Case 1: length of K is different from N
    if len(K_digits) < N:
        # Generate the smallest possible number with available digits
        digits = []
        for d in range(1, 10):
            digits.extend([str(d)] * counts[d])
        digits.sort()
        print(''.join(digits))
        return
    elif len(K_digits) > N:
        print(-1)
        return

    # Case 2: length is same, check if max possible (sorted descending) is <= K
    max_digits = []
    for d in range(9, 0, -1):
        max_digits.extend([str(d)] * counts[d])
    max_num = ''.join(max_digits)
    if max_num <= K:
        print(-1)
        return

    # Case 3: Need to find minimal M > K
    # Simulate building M by matching K's digits
    current_counts = counts.copy()
    matched_prefix = []
    found_larger = False
    for i in range(N):
        current_k_digit = K_digits[i]
        k_num = int(current_k_digit)
        if current_counts[k_num] > 0:
            # Tentatively use this digit
            current_counts[k_num] -= 1
            matched_prefix.append(current_k_digit)
        else:
            # Need to find a larger digit
            found_larger_digit = False
            for d in range(k_num + 1, 10):
                if current_counts[d] > 0:
                    # Use this digit, then append remaining in sorted order
                    current_counts[d] -= 1
                    suffix = []
                    for num in range(1, 10):
                        suffix.extend([str(num)] * current_counts[num])
                    suffix.sort()
                    M = ''.join(matched_prefix) + str(d) + ''.join(suffix)
                    print(M)
                    return
            # No larger digit found here, backtrack needed but not possible with N large.
            # Since max_num > K, must have found earlier
            # This code is unreachable because we checked max_num > K
            break
    # All digits matched, check if formed number is K
    M_formed = ''.join(matched_prefix)
    if M_formed == K:
        # Generate next permutation of K's digits
        def next_permutation(s):
            s_list = list(s)
            i = len(s_list) - 2
            while i >= 0 and s_list[i] >= s_list[i + 1]:
                i -= 1
            if i < 0:
                return None
            j = len(s_list) - 1
            while s_list[j] <= s_list[i]:
                j -= 1
            s_list[i], s_list[j] = s_list[j], s_list[i]
            s_list[i + 1:] = reversed(s_list[i + 1:])
            return ''.join(s_list)
        next_m = next_permutation(K)
        print(next_m)
    else:
        print(M_formed)
    return

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