結果

問題 No.1630 Sorting Integers (Greater than K)
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:36:16
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,504 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 64,044 KB
最終ジャッジ日時 2025-06-12 16:36:22
合計ジャッジ時間 5,385 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 11 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    K = input[idx]
    idx += 1
    c = list(map(int, input[idx:idx+9]))
    idx += 9
    
    original_counts = [0] * 10  # 0 is dummy
    for i in range(1, 10):
        original_counts[i] = c[i-1]
    
    # Case 1: len(K) != N
    if len(K) != N:
        if len(K) > N:
            print(-1)
            return
        else:
            # len(K) < N, generate smallest possible N-digit number
            has_non_zero = False
            for d in range(1, 10):
                if original_counts[d] > 0:
                    has_non_zero = True
                    break
            if not has_non_zero:
                print(-1)
                return
            # Find the smallest non-zero digit
            first_d = None
            for d in range(1, 10):
                if original_counts[d] > 0:
                    first_d = d
                    break
            remaining = original_counts.copy()
            remaining[first_d] -= 1
            rest = []
            for d in range(1, 10):
                if remaining[d] > 0:
                    rest.append(str(d) * remaining[d])
            rest_str = ''.join(rest)
            result = str(first_d) + rest_str
            print(result)
            return
    
    # Case 2: len(K) == N
    # Precompute prefix_counts
    prefix_counts = [ [0]*10 for _ in range(N+1) ]
    for i in range(1, N+1):
        current_d = int(K[i-1])
        for d in range(10):
            prefix_counts[i][d] = prefix_counts[i-1][d]
        prefix_counts[i][current_d] += 1
    
    possible_prefix = [False] * (N+1)
    possible_prefix[0] = True
    for i in range(1, N+1):
        valid = True
        for d in range(1, 10):
            if prefix_counts[i][d] > original_counts[d]:
                valid = False
                break
        possible_prefix[i] = valid
    
    current_min = None
    
    for i in range(N):
        if not possible_prefix[i]:
            continue
        # Compute available counts after using prefix up to i-1
        available = original_counts.copy()
        for d in range(1, 10):
            available[d] -= prefix_counts[i][d]
        current_digit = int(K[i])
        # Find smallest d > current_digit with available[d] > 0
        min_d = None
        for d in range(current_digit + 1, 10):
            if available[d] > 0:
                min_d = d
                break
        if min_d is None:
            continue
        # Check if sum of available after subtracting min_d is N - i -1
        # But since sum(available) is sum(original) - sum(prefix_counts[i]) = N - sum(prefix_counts[i])
        # sum(prefix_counts[i]) is i (since prefix is K[0..i-1], i digits)
        # sum(available) = N - i
        # after subtracting 1 from min_d, sum becomes N - i -1, which is correct
        available[min_d] -= 1
        # Generate suffix
        suffix = []
        for d in range(1, 10):
            if available[d] > 0:
                suffix.append(str(d) * available[d])
        suffix_str = ''.join(suffix)
        candidate = K[:i] + str(min_d) + suffix_str
        if len(candidate) != N:
            continue  # should not happen
        if candidate > K:
            if current_min is None or candidate < current_min:
                current_min = candidate
    
    if current_min is not None:
        print(current_min)
    else:
        print(-1)

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