結果

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

ソースコード

diff # 

from fractions import Fraction
from itertools import combinations
from sys import stdin

def main():
    input = stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    entire_set = frozenset(A)
    memo = {}

    def compute_values(s):
        if s in memo:
            return memo[s]
        if len(s) == 1:
            val = next(iter(s))
            res = {Fraction(val)}
            memo[s] = res
            return res
        possible = set()
        elements = sorted(list(s))
        first_element = elements[0]
        n = len(elements)
        for l in range(1, n):
            for indices in combinations(range(n), l):
                if 0 not in indices:
                    continue
                subset_elements = [elements[i] for i in indices]
                s1 = frozenset(subset_elements)
                s2 = s - s1
                if not s2:
                    continue
                vals1 = compute_values(s1)
                vals2 = compute_values(s2)
                for v1 in vals1:
                    for v2 in vals2:
                        possible.add(v1 + v2)
                        possible.add(v1 - v2)
                        possible.add(v2 - v1)
                        possible.add(v1 * v2)
                        if v2 != 0:
                            possible.add(v1 / v2)
                        if v1 != 0:
                            possible.add(v2 / v1)
        memo[s] = possible
        return possible

    elements = sorted(A)
    first_element = elements[0]
    found = False
    for l in range(1, len(elements)):
        for indices in combinations(range(len(elements)), l):
            if 0 not in indices:
                continue
            subset = [elements[i] for i in indices]
            s1 = frozenset(subset)
            s2 = entire_set - s1
            if not s2:
                continue
            vals1 = compute_values(s1)
            vals2 = compute_values(s2)
            if vals1 & vals2:
                found = True
                print("YES")
                return
    print("NO")

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