結果
問題 | No.2895 Zero XOR Subset |
ユーザー |
![]() |
提出日時 | 2024-09-20 22:10:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 152 ms / 2,000 ms |
コード長 | 1,719 bytes |
コンパイル時間 | 398 ms |
コンパイル使用メモリ | 82,192 KB |
実行使用メモリ | 106,404 KB |
最終ジャッジ日時 | 2024-09-20 22:11:55 |
合計ジャッジ時間 | 5,344 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 35 |
ソースコード
class xor_base(): def __init__(self): self.K = 60 self._list = [0] * self.K self.cnt = 0 def min_all(self, x): for i in range(self.K - 1, -1, -1): if (x >> i) & 1: x ^= self._list[i] return x def add(self, x): x = self.min_all(x) if x == 0: return 0 for i in range(self.K - 1, -1, -1): if (x >> i) & 1: for j in range(self.K): if (self._list[j] >> i) & 1: self._list[j] ^= x self._list[i] = x self.cnt += 1 return 1 return 0 def get(self, x): now = 0 for i in range(self.K): if self._list[i] == 0: continue if x & 1: now ^= self._list[i] x >>= 1 return now def __len__(self): return self.cnt def __str__(self): return f"{self._list}, len = {self.cnt}" N = int(input()) A = list(map(int, input().split())) X = xor_base() XX = [] XX.append(X) from copy import * now = -1 ans = [] for i, a in enumerate(A): if a == 0: print(1) print(i + 1) exit() if not X.add(a): now = a ans.append(i+1) break else: XX.append(deepcopy(X)) else: print(-1) exit() ind = ans[-1] - 1 for i in range(ind, 0, -1): if not XX[i - 1].add(now ^ A[i - 1]): ans.append(i) now ^= A[i - 1] if now == 0: break ans.sort() if now == 0: print(len(ans)) print(*ans) else: print(-1)