結果

問題 No.1630 Sorting Integers (Greater than K)
ユーザー lam6er
提出日時 2025-03-31 17:52:51
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,892 bytes
コンパイル時間 219 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 383,436 KB
最終ジャッジ日時 2025-03-31 17:53:55
合計ジャッジ時間 5,258 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 11 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    N, K = sys.stdin.readline().split()
    N = int(N)
    c = list(map(int, sys.stdin.readline().split()))
    c = [0] + c  # c[1] to c[9]

    if len(K) != N:
        if len(K) > N:
            print(-1)
            return
        else:
            digits = []
            for d in range(1, 10):
                digits.extend([str(d)] * c[d])
            if not digits or len(digits) != N:
                print(-1)
                return
            digits.sort()
            print(''.join(digits))
            return

    # Now, handle case when N == len(K)
    # Precompute frequency array
    freq = [[0]*10 for _ in range(N+1)]
    for i in range(N):
        current_d = int(K[i])
        for d in range(1, 10):
            freq[i+1][d] = freq[i][d]
        freq[i+1][current_d] += 1

    min_candidate = None

    for i in range(N):
        current_digit = int(K[i])
        available = [c[d] - freq[i][d] for d in range(10)]

        # Check for digits greater than current_digit
        found = False
        for d in range(current_digit + 1, 10):
            if available[d] > 0:
                temp_available = available.copy()
                temp_available[d] -= 1
                suffix = []
                for digit in range(1, 10):
                    suffix.extend([str(digit)] * temp_available[digit])
                if len(suffix) != N - i - 1:
                    continue
                candidate = K[:i] + str(d) + ''.join(suffix)
                if (min_candidate is None) or (candidate < min_candidate):
                    min_candidate = candidate
                found = True
                break  # since we choose smallest d
        if found:
            continue  # proceed to check other positions

    if min_candidate is not None:
        print(min_candidate)
    else:
        print(-1)

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