#1059721 (PyPy3) No.332 数列をプレゼントに

• 問題: No.332 数列をプレゼントに
• ユーザー: lam6er
• 提出日時: 2025-03-26 16:00:15
• 言語: PyPy3 (7.3.15)
• 結果: TLE
• 実行時間: -
• コード長: 2,742 bytes
• コンパイル時間: 378 ms
• コンパイル使用メモリ: 82,680 KB
• 実行使用メモリ: 85,292 KB
• 最終ジャッジ日時: 2025-03-26 16:01:20
• 合計ジャッジ時間: 4,363 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
sample	AC * 5
other	AC * 1 TLE * 1 -- * 40

ソースコード

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
92
93
94
95
96
97
def main():
    import sys
    from itertools import combinations
    n, x = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    
    # Filter out elements greater than X and check for elements equal to X
    filtered = []
    for num in a:
        if num == x:
            # Directly output the result if found
            res = ['x'] * n
            for i in range(n):
                if a[i] == x:
                    res[i] = 'o'
                    print(''.join(res))
                    return
        if num <= x:
            filtered.append(num)
    
    # If no elements left after filtering
    if not filtered:
        print("No")
        return
    
    # Check if sum of filtered equals X
    total = sum(filtered)
    if total == x:
        res = []
        for num in a:
            if num > x:
                res.append('x')
            else:
                res.append('o')
        print(''.join(res))
        return
    if total < x:
        print("No")
        return
    
    # Now, check for subset sum
    len_filtered = len(filtered)
    indices = [i for i, num in enumerate(a) if num <= x]
    filtered_with_indices = [(num, idx) for num, idx in zip(filtered, indices)]
    
    # Function to generate all possible subset sums and their indices
    def generate_sums(arr):
        sums = {}
        n = len(arr)
        for i in range(1 << n):
            s = 0
            idxs = []
            for j in range(n):
                if (i >> j) & 1:
                    s += arr[j][0]
                    idxs.append(arr[j][1])
            if s not in sums:
                sums[s] = idxs
            # Prefer smaller subsets in case of multiple possibilities
            if len(idxs) < len(sums[s]):
                sums[s] = idxs
        return sums
    
    # Split into two halves
    half = len_filtered // 2
    first_half = filtered_with_indices[:half]
    second_half = filtered_with_indices[half:]
    
    sum1 = generate_sums(first_half)
    sum2 = generate_sums(second_half)
    
    found = False
    best = None
    for s1 in sum1:
        s2 = x - s1
        if s2 in sum2:
            # Combine the indices
            idxs = sum1[s1] + sum2[s2]
            if not best or len(idxs) < len(best):
                best = idxs
            found = True
    
    if found:
        res = ['x'] * n
        for idx in best:
            res[idx] = 'o'
        print(''.join(res))
        return
    
    # If len(filtered) > 40, then each element is small (product constraint)
    # But we have to handle it, but previous code already handles meet-in-middle for len <=40
    # So if we reach here, answer is No
    print("No")
if __name__ == "__main__":
    main()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX