結果
| 問題 |
No.1630 Sorting Integers (Greater than K)
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:11:03 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,843 bytes |
| コンパイル時間 | 161 ms |
| コンパイル使用メモリ | 82,192 KB |
| 実行使用メモリ | 286,680 KB |
| 最終ジャッジ日時 | 2025-05-14 13:13:15 |
| 合計ジャッジ時間 | 4,725 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 11 TLE * 1 -- * 10 |
ソースコード
import sys
from collections import Counter
# Use sys.stdin.readline for faster input processing
input = sys.stdin.readline
def solve():
# Read N and K. N is the total number of digits, K is the target integer as a string.
N_str, K_str = input().split()
N = int(N_str)
# Read the counts of digits 1 through 9.
counts_list = list(map(int, input().split()))
# Store counts in a Counter dictionary for efficient lookup and modification.
# Keys are digit characters '1' through '9'.
C = Counter()
for i in range(9):
digit_char = str(i+1)
C[digit_char] = counts_list[i]
# Calculate the length of K.
L = len(K_str)
# Case 1: N > L
# If the number of available digits N is greater than the number of digits in K (L),
# any N-digit number M formed will be greater than K.
# We want the smallest such M, which is formed by sorting the available digits non-decreasingly.
if N > L:
ans_parts = [] # Use a list to collect characters
# Iterate through digits 1 to 9
for d_val in range(1, 10):
d = str(d_val)
count = C[d]
if count > 0:
# Append the character d, count times
ans_parts.extend([d] * count)
# Join the characters to form the final string and print
print("".join(ans_parts))
return
# Case 2: N < L
# If N is less than L, any N-digit number M will be smaller than K.
# Therefore, no M > K exists.
if N < L:
print("-1")
return
# Case 3: N = L
# This is the main case where we need to find the smallest M > K using the given digits.
# Keep track of the counts of available digits as we build the prefix of M.
current_counts = C.copy()
# Store the prefix digits of M constructed so far as a list of characters.
prefix_digits = []
# Stores the best candidate M found so far. We want the overall minimum M > K.
# The logic ensures that the last candidate found corresponds to the longest possible matching prefix with K,
# which results in the minimal M > K.
best_M_found = None
# Iterate through positions from left to right (index 0 to N-1).
for i in range(N):
# Get the digit k_i from K at the current position i.
k_i = K_str[i]
# Take a snapshot of the current digit counts before trying to find a pivot digit.
# This is needed because if we find a pivot and generate a candidate M,
# we still need to check if we could have matched k_i and continued.
current_counts_before_pivot_check = current_counts.copy()
# Try finding the smallest available digit 'd' such that d > k_i.
# This 'd' would be the 'pivot' digit at position i, making M > K.
pivot_d = None
# Convert k_i char to integer for comparison. Handles '0' through '9'.
k_i_val = int(k_i)
# Check digits from k_i + 1 up to 9.
for d_val in range(k_i_val + 1, 10):
d = str(d_val)
# Check if digit d is available (count > 0).
if current_counts[d] > 0:
pivot_d = d # Found the smallest available digit d > k_i
break # Stop searching for d
# If a pivot digit 'd' was found:
if pivot_d is not None:
# We found a way to make M > K starting at this position i.
# Construct the candidate M: prefix + pivot_d + smallest possible suffix.
# Create temporary counts to calculate the suffix. Start from current counts.
temp_counts = current_counts.copy()
temp_counts[pivot_d] -= 1 # Use the pivot digit 'd'.
# Build the suffix using the remaining available digits, sorted non-decreasingly.
suffix_chars = []
for suffix_d_val in range(1, 10):
suffix_d = str(suffix_d_val)
count = temp_counts[suffix_d]
if count > 0:
# Append suffix_d character 'count' times.
suffix_chars.extend([suffix_d] * count)
# Combine prefix, pivot digit, and suffix to form the full candidate M string.
# Store this candidate. Because we iterate i from left to right, the last candidate generated
# will correspond to the longest prefix match with K, resulting in the minimal M > K.
best_M_found = "".join(prefix_digits) + pivot_d + "".join(suffix_chars)
# Regardless of finding a pivot, check if we could have matched k_i at this position.
# Use the counts state from *before* the pivot check.
if current_counts_before_pivot_check[k_i] > 0:
# If k_i is available, consume it to continue matching K's prefix.
current_counts = current_counts_before_pivot_check # Restore counts state.
current_counts[k_i] -= 1 # Decrement count for k_i.
prefix_digits.append(k_i) # Add k_i to the prefix being built.
else:
# If k_i is not available, we cannot continue matching K's prefix.
# Any M > K must have already been found (by finding a pivot d > k_j at some j <= i).
# If no pivot was found up to this point, no M > K exists that matches K up to i-1.
break # Stop the loop.
# After the loop finishes:
if best_M_found is None:
# If no candidate M was found, it means either M=K was the only possibility using the digits,
# or no permutation M >= K could be formed. In either case, no M > K exists.
print("-1")
else:
# Otherwise, print the best candidate found.
print(best_M_found)
# Call the solve function to run the logic.
solve()