結果

問題 No.3024 全単射的
ユーザー gew1fw
提出日時 2025-06-12 20:52:00
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,690 bytes
コンパイル時間 194 ms
コンパイル使用メモリ 82,076 KB
実行使用メモリ 66,952 KB
最終ジャッジ日時 2025-06-12 20:56:23
合計ジャッジ時間 2,652 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    total_mask = (1 << N) - 1

    dp = defaultdict(set)
    for i in range(N):
        mask = 1 << i
        dp[mask].add(A[i])

    # Generate masks in order of increasing number of bits
    masks = []
    for mask in range(1, 1 << N):
        cnt = bin(mask).count('1')
        masks.append((cnt, mask))
    masks.sort()

    for cnt, mask in masks:
        s = (mask - 1) & mask
        while s > 0:
            t = mask ^ s
            if s < t:  # Avoid processing the same pair twice
                if s in dp and t in dp:
                    for a in dp[s]:
                        for b in dp[t]:
                            # Addition
                            dp[mask].add(a + b)
                            # Multiplication
                            dp[mask].add(a * b)
                            # Subtraction
                            dp[mask].add(a - b)
                            dp[mask].add(b - a)
                            # Division
                            if b != 0 and a % b == 0:
                                dp[mask].add(a // b)
                            if a != 0 and b % a == 0:
                                dp[mask].add(b // a)
            s = (s - 1) & mask

    # Check all possible splits of the full set
    for s in range(1, total_mask):
        t = total_mask ^ s
        if s > t:
            continue
        if s not in dp or t not in dp:
            continue
        if dp[s] & dp[t]:
            print("YES")
            return
    print("NO")

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