結果

問題 No.1630 Sorting Integers (Greater than K)
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:17:27
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,562 bytes
コンパイル時間 253 ms
コンパイル使用メモリ 82,504 KB
実行使用メモリ 95,900 KB
最終ジャッジ日時 2025-06-12 21:17:56
合計ジャッジ時間 2,792 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 15 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

def next_permutation(s):
    s = list(s)
    i = len(s) - 2
    while i >= 0 and s[i] >= s[i + 1]:
        i -= 1
    if i == -1:
        return None
    j = len(s) - 1
    while j > i and s[j] <= s[i]:
        j -= 1
    s[i], s[j] = s[j], s[i]
    s[i + 1:] = reversed(s[i + 1:])
    return ''.join(s)

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    K = input[1]
    counts = list(map(int, input[2:11]))
    counts = [0] + counts  # counts[1..9] correspond to digits 1..9

    if len(K) < N:
        digits = []
        for d in range(1, 10):
            digits.extend([str(d)] * counts[d])
        digits.sort()
        if not digits:
            print(-1)
        else:
            print(''.join(digits))
        return
    elif len(K) > N:
        print(-1)
        return
    else:
        # Check if K can be formed with the counts
        copy_counts = counts.copy()
        can_form = True
        for i in range(len(K)):
            digit = int(K[i])
            if copy_counts[digit] <= 0:
                can_form = False
                break
            copy_counts[digit] -= 1
        if can_form:
            next_p = next_permutation(K)
            if next_p is not None:
                print(next_p)
            else:
                print(-1)
            return
        else:
            # Find the first position where K's digit is not available
            copy_counts = counts.copy()
            pos = 0
            for i in range(len(K)):
                digit = int(K[i])
                if copy_counts[digit] <= 0:
                    pos = i
                    break
                copy_counts[digit] -= 1
            else:
                # This should not happen since can_form is False
                print(-1)
                return

            current_digit = int(K[pos])
            available_digits = []
            for d in range(1, 10):
                if copy_counts[d] > 0:
                    available_digits.append(d)
            possible_ds = [d for d in available_digits if d > current_digit]
            if not possible_ds:
                print(-1)
                return
            d = min(possible_ds)
            copy_counts[d] -= 1
            remaining = []
            for digit in range(1, 10):
                remaining.extend([str(digit)] * copy_counts[digit])
            remaining.sort()
            prefix = K[:pos] + str(d)
            suffix = ''.join(remaining)
            print(prefix + suffix)
            return

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