結果

問題 No.2121 帰属関係と充足可能性
ユーザー lam6er
提出日時 2025-03-20 20:45:20
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,120 bytes
コンパイル時間 148 ms
コンパイル使用メモリ 82,604 KB
実行使用メモリ 66,492 KB
最終ジャッジ日時 2025-03-20 20:45:32
合計ジャッジ時間 4,235 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 TLE * 1 -- * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

def generate_V(n):
    if n == 0:
        return [frozenset()]
    prev = generate_V(n - 1)
    current = []
    from itertools import combinations
    prev_list = list(prev)
    # Generate all possible subsets of the previous V_{n-1}
    for bits in range(1 << len(prev_list)):
        subset = []
        for i in range(len(prev_list)):
            if (bits >> i) & 1:
                subset.append(prev_list[i])
        current.append(frozenset(subset))
    # Remove duplicates by converting to a set first
    unique = []
    seen = set()
    for s in current:
        if s not in seen:
            seen.add(s)
            unique.append(s)
    return unique

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:7]))
    A0, A1, A2, A3, A4, A5 = A

    Vn = generate_V(N)

    for m0 in Vn:
        for m1 in Vn:
            for m2 in Vn:
                # Determine which variables to check based on A0-A5
                mA0 = [m0, m1, m2][A0]
                mA1_set = [m0, m1, m2][A1]
                mA2 = [m0, m1, m2][A2]
                mA3_val = [m0, m1, m2][A3]
                mA4_val = [m0, m1, m2][A4]
                mA5_val = [m0, m1, m2][A5]

                # Check condition 1: mA0 subset of mA1
                cond1 = True
                for x in Vn:
                    if x in mA0 and x not in mA1_set:
                        cond1 = False
                        break
                if not cond1:
                    continue

                # Check condition2: mA1 in mA2
                if mA1_set not in mA2:
                    continue

                # Check condition3: A3's variable in mA2
                if mA3_val not in mA2:
                    continue

                # Check condition4: A4's variable in mA2
                if mA4_val not in mA2:
                    continue

                # Check condition5: A5's variable in mA0
                if mA5_val not in mA0:
                    continue

                print("YES")
                return
    print("NO")

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