結果

問題 No.2061 XOR Sort
ユーザー lam6er
提出日時 2025-04-15 21:51:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 855 ms / 2,000 ms
コード長 1,312 bytes
コンパイル時間 416 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 293,696 KB
最終ジャッジ日時 2025-04-15 21:53:29
合計ジャッジ時間 11,480 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

n = int(input())
a = list(map(int, input().split()))
distinct = list(sorted(set(a)))

if len(distinct) <= 1:
    print(1)
else:
    current_groups = [distinct.copy()]
    answer = 1

    for bit in reversed(range(30)):  # Process from highest bit (29) to 0
        can_split = False
        # Check if any group can be split at this bit
        for group in current_groups:
            if len(group) <= 1:
                continue
            first_bit = (group[0] >> bit) & 1
            for num in group[1:]:
                if (num >> bit) & 1 != first_bit:
                    can_split = True
                    break
            if can_split:
                break
        if can_split:
            answer = (answer * 2) % MOD
        
        # Split all groups into subgroups based on current bit
        new_groups = []
        for group in current_groups:
            subgroup0 = []
            subgroup1 = []
            for num in group:
                if (num >> bit) & 1 == 0:
                    subgroup0.append(num)
                else:
                    subgroup1.append(num)
            if subgroup0:
                new_groups.append(subgroup0)
            if subgroup1:
                new_groups.append(subgroup1)
        current_groups = new_groups

    print(answer)
0