結果

問題 No.2270 T0空間
ユーザー lam6er
提出日時 2025-03-31 17:21:27
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,408 bytes
コンパイル時間 250 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 89,308 KB
最終ジャッジ日時 2025-03-31 17:23:02
合計ジャッジ時間 10,157 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 16 TLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys

def main():
    n = int(sys.stdin.readline())
    m = int(sys.stdin.readline())
    s_list = [sys.stdin.readline().strip() for _ in range(m)]
    
    # Convert each string to an integer representing its bits, right to left
    s_masks = []
    for s in s_list:
        rev_s = s[::-1]
        mask = int(rev_s, 2)
        s_masks.append(mask)
    
    # covered[i][j] is True if the pair (i,j) is covered, where i < j
    covered = [ [False]*(n+1) for _ in range(n+1) ]
    total_pairs = n * (n - 1) // 2
    remaining = total_pairs
    
    for s_mask in s_masks:
        # List comprehension to find ones and zeros (1-based positions)
        ones = [i + 1 for i in range(n) if (s_mask >> i) & 1]
        zeros = [i + 1 for i in range(n) if not ((s_mask >> i) & 1)]
        if not ones or not zeros:
            continue  # This s contributes nothing
        
        # Iterate all combinations of ones and zeros to generate pairs
        for a in ones:
            for b in zeros:
                i, j = (a, b) if a < b else (b, a)
                if i >= j:
                    continue
                if not covered[i][j]:
                    covered[i][j] = True
                    remaining -= 1
                    if remaining == 0:
                        print("Yes")
                        return
    print("Yes" if remaining == 0 else "No")

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