結果

問題 No.2061 XOR Sort
コンテスト
ユーザー LyricalMaestro
提出日時 2026-10-11 17:32:33
言語 PyPy3
(8.0.0 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 304 ms / 2,000 ms
+ 403µs
コード長 1,462 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 608 ms
コンパイル使用メモリ 81,024 KB
実行使用メモリ 191,732 KB
最終ジャッジ日時 2026-10-11 17:32:41
合計ジャッジ時間 7,696 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/2061

MOD = 998244353

def solve(N, A):
    A.sort()

    groups = [(0, N)]
    answer = 1
    for k in reversed(range(30)):
        is_changes = False
        new_groups = []
        for low, high in groups:
            left = -1
            right = -1
            for i in range(low, high):
                if A[i] & (1 << k) == 0:
                    if left == -1:
                        left = i
                else:
                    if right == -1:
                        right = i

            if left != -1 and right != -1:
                is_changes = True
                new_groups.append((left, right))
                new_groups.append((right, high))
            elif left != -1:
                new_groups.append((left, high))
            elif right != -1:
                new_groups.append((right, high))

        if is_changes:
            answer *= 2
            answer %= MOD
        groups = new_groups
    print(answer)


def solve2(N, A):
    t_set = set()
    for x in range(100):
        B = []
        for a in A:
            B.append(a ^ x)
        B.sort()
        ans = []
        for b in B:
            ans.append(b ^ x)
        t_set.add(tuple(ans))
    print(len(t_set))
        


def main():
    N = int(input())
    A = list(map(int, input().split()))


    solve(N, A)
#    solve2(N, A)
            

            


            
            






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