結果

問題 No.2061 XOR Sort
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:37:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 477 ms / 2,000 ms
コード長 1,181 bytes
コンパイル時間 184 ms
コンパイル使用メモリ 81,536 KB
実行使用メモリ 198,916 KB
最終ジャッジ日時 2025-04-16 15:42:50
合計ジャッジ時間 7,498 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    a = list(map(int, input[1:n+1]))
    
    groups = [a]
    ans = 1
    
    for k in reversed(range(30)):  # from 29 downto 0
        new_groups = []
        flag = False
        for group in groups:
            split = False
            val = None
            for num in group:
                bit = (num >> k) & 1
                if val is None:
                    val = bit
                else:
                    if bit != val:
                        split = True
                        break
            if split:
                group0 = []
                group1 = []
                for num in group:
                    if (num >> k) & 1:
                        group1.append(num)
                    else:
                        group0.append(num)
                new_groups.append(group0)
                new_groups.append(group1)
                flag = True
            else:
                new_groups.append(group)
        if flag:
            ans = (ans * 2) % MOD
        groups = new_groups
    print(ans % MOD)

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