結果
問題 |
No.1192 半部分列
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:56:28 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,106 bytes |
コンパイル時間 | 210 ms |
コンパイル使用メモリ | 82,712 KB |
実行使用メモリ | 76,296 KB |
最終ジャッジ日時 | 2025-06-12 20:59:51 |
合計ジャッジ時間 | 2,627 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 WA * 15 |
ソースコード
def find_min_subsequence(S, T): # Step 1: Check if any character in S is not present in T t_set = set(T) candidates = [] for c in S: if c not in t_set: candidates.append(c) if candidates: return min(candidates) # Step 2: Check if S is a subsequence of T def is_subsequence(s, t): i = j = 0 len_s = len(s) len_t = len(t) while i < len_s and j < len_t: if s[i] == t[j]: i += 1 j += 1 else: j += 1 return i == len_s if is_subsequence(S, T): return -1 # Step 3: Binary search to find the minimal k low = 1 high = len(S) answer = None while low <= high: mid = (low + high) // 2 prefix = S[:mid] if is_subsequence(prefix, T): low = mid + 1 else: answer = prefix high = mid - 1 return answer # Read input S = input().strip() T = input().strip() result = find_min_subsequence(S, T) print(result if result is not None else -1)