結果
問題 | No.2895 Zero XOR Subset |
ユーザー |
|
提出日時 | 2024-09-19 20:12:38 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 111 ms / 2,000 ms |
コード長 | 805 bytes |
コンパイル時間 | 205 ms |
コンパイル使用メモリ | 82,424 KB |
実行使用メモリ | 106,804 KB |
最終ジャッジ日時 | 2024-09-19 21:53:08 |
合計ジャッジ時間 | 4,530 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 35 |
ソースコード
n = int(input())a = list(map(int, input().split()))assert 1 <= n <= 2 * 10**5assert len(a) == nassert all(0 <= x < 1 << 60 for x in a)if n > 61:n = 61a = a[:61]idx_list = [{i} for i, _ in enumerate(a)]pivot = 0for i in range(60):for j in range(pivot, n):if a[j] & (1 << i):a[pivot], a[j] = a[j], a[pivot]idx_list[pivot], idx_list[j] = idx_list[j], idx_list[pivot]breakelse:continuefor j in range(n):if j == pivot:continueif a[j] & (1 << i):a[j] ^= a[pivot]idx_list[j] ^= idx_list[pivot]pivot += 1if 0 in a:zero_idx = a.index(0)b = [i + 1 for i in idx_list[zero_idx]]print(len(b))print(*sorted(b))else:print(-1)