#1061948 (PyPy3) No.1192 半部分列

• 問題: No.1192 半部分列
• ユーザー: lam6er
• 提出日時: 2025-03-31 17:42:33
• 言語: PyPy3 (7.3.15)
• 結果: WA
• 実行時間: -
• コード長: 3,236 bytes
• コンパイル時間: 284 ms
• コンパイル使用メモリ: 82,316 KB
• 実行使用メモリ: 173,120 KB
• 最終ジャッジ日時: 2025-03-31 17:43:37
• 合計ジャッジ時間: 4,890 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 19 WA * 6

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
from collections import defaultdict
import bisect
def main():
    s = input().strip()
    t = input().strip()
    # Preprocess S: store positions for each character
    s_pos = defaultdict(list)
    for idx, c in enumerate(s):
        s_pos[c].append(idx)
    
    n = len(t)
    # Preprocess T: build next_pos array
    # next_pos[i][c] is the next position of character 'c' starting from index i in T
    next_pos = [{} for _ in range(n + 2)]  # +2 to handle i = n and i = n+1
    # Initialize for position n (all characters have next_pos as n)
    next_pos[n] = {chr(ord('a') + i): n for i in range(26)}
    # Build next_pos from the end of T backwards
    for i in range(n - 1, -1, -1):
        current = next_pos[i + 1].copy()
        current_char = t[i]
        current[current_char] = i
        next_pos[i] = current
    
    result = []
    current_t_pos = -1  # Last matched position in T
    i = 0  # Current position in S
    len_s = len(s)
    found_any = False  # Flag to check if any candidate was considered
    while i < len_s:
        found = False
        for c in 'abcdefghijklmnopqrstuvwxyz':
            # Find the first occurrence of c in s[i:]
            pos_list = s_pos.get(c, [])
            if not pos_list:
                continue  # No occurrence of this character
            # Find the first index >= i using binary search
            idx = bisect.bisect_left(pos_list, i)
            if idx == len(pos_list):
                continue  # No occurrence in the remaining part
            j = pos_list[idx]
            # Calculate next position in T
            current_t_next = current_t_pos + 1
            if current_t_next < 0:
                current_t_next = 0  # Handle initial case where current_t_pos is -1
            if current_t_next > n:
                next_t = n
            else:
                next_t = next_pos[current_t_next].get(c, n)
            
            if next_t < n:
                # Check if there are characters left in S after j
                if j + 1 < len_s:
                    # Can choose this c, and continue to build the result
                    result.append(c)
                    current_t_pos = next_t
                    i = j + 1
                    found = True
                    found_any = True
                    break
                else:
                    # No remaining characters, but this c would make a subsequence of T
                    # So skip this c
                    continue
            else:
                # Choosing c will make the result not a subsequence of T
                result.append(c)
                print(''.join(result))
                return
        if not found:
            break  # No valid characters could be chosen; break the loop
    
    # After building the result, check if it's not a subsequence of T
    # Also handle cases where no characters were chosen but possible empty string case
    def is_subsequence(sub, t_str):
        it = iter(t_str)
        return all(char in it for char in sub)
    
    if not result:
        print(-1)
    else:
        if is_subsequence(result, t):
            print(-1)
        else:
            print(''.join(result))
if __name__ == "__main__":
    main()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX