結果

問題 No.3024 全単射的
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:10:54
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,875 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 82,636 KB
実行使用メモリ 89,344 KB
最終ジャッジ日時 2025-06-12 16:11:01
合計ジャッジ時間 4,913 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

from fractions import Fraction

def main():
    import sys
    from sys import stdin
    N = int(stdin.readline())
    A = list(map(int, stdin.readline().split()))
    if N < 2:
        print("NO")
        return
    memo = {}
    found = False
    # Iterate through all possible non-empty subsets except the full set
    for mask in range(1, (1 << N) - 1):
        S = []
        T = []
        for i in range(N):
            if (mask >> i) & 1:
                S.append(A[i])
            else:
                T.append(A[i])
        if not S or not T:
            continue
        s_values = compute(S, memo)
        t_values = compute(T, memo)
        if s_values & t_values:
            print("YES")
            found = True
            break
    if not found:
        print("NO")

def compute(nums, memo):
    key = tuple(sorted(nums))
    if key in memo:
        return memo[key]
    if len(nums) == 1:
        res = {Fraction(nums[0], 1)}
        memo[key] = res
        return res
    res = set()
    first = nums[0]
    remaining = nums[1:]
    n = len(remaining)
    for mask in range(0, (1 << n)):
        a_rest = []
        b_rest = []
        for j in range(n):
            if (mask >> j) & 1:
                a_rest.append(remaining[j])
            else:
                b_rest.append(remaining[j])
        A_part = [first] + a_rest
        B_part = b_rest
        if not A_part or not B_part:
            continue
        setA = compute(A_part, memo)
        setB = compute(B_part, memo)
        for x in setA:
            for y in setB:
                res.add(x + y)
                res.add(x - y)
                res.add(y - x)
                res.add(x * y)
                if y != 0:
                    res.add(x / y)
                if x != 0:
                    res.add(y / x)
    memo[key] = res
    return res

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