結果

問題 No.1900 Don't be Powers of 2
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:08:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,089 bytes
コンパイル時間 176 ms
コンパイル使用メモリ 82,580 KB
実行使用メモリ 77,092 KB
最終ジャッジ日時 2025-03-20 21:08:53
合計ジャッジ時間 3,898 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))

    count = defaultdict(int)
    for num in a:
        count[num] += 1

    # Precompute cnt for each element
    cnt = [0] * n
    for i in range(n):
        ai = a[i]
        current_cnt = 0
        for k in range(30):
            target = ai ^ (1 << k)
            current_cnt += count.get(target, 0)
        cnt[i] = current_cnt

    # Sort indices based on cnt, then value to break ties
    sorted_indices = sorted(range(n), key=lambda x: (cnt[x], a[x]))

    max_size = 0
    selected = []

    for idx in sorted_indices:
        current_num = a[idx]
        valid = True
        for s in selected:
            xor = current_num ^ s
            if xor & (xor - 1) == 0 and xor != 0:
                valid = False
                break
        if valid:
            selected.append(current_num)
            if len(selected) > max_size:
                max_size = len(selected)

    print(max_size)

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