結果
問題 |
No.2895 Zero XOR Subset
|
ユーザー |
|
提出日時 | 2024-10-29 18:24:20 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 1,129 bytes |
コンパイル時間 | 13,878 ms |
コンパイル使用メモリ | 401,864 KB |
実行使用メモリ | 7,296 KB |
最終ジャッジ日時 | 2024-10-29 18:24:37 |
合計ジャッジ時間 | 16,198 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 35 |
ソースコード
use std::collections::HashSet; use proconio::input; fn main() { input! { n:usize, mut a:[usize;n], } const D: usize = 60; let n = if n > 100 { 100 } else { n }; let mut hists = vec![]; for i in 0..n { let mut hs = HashSet::new(); hs.insert(i); hists.push(hs); } let mut rank = 0; for col in 0..D { let Some(row)=(rank..n).find(|&row|a[row]&(1<<col)!=0)else{ continue; }; hists.swap(row, rank); a.swap(row, rank); for i in 0..n { if rank == i || a[i] & (1 << col) == 0 { continue; } a[i] ^= a[rank]; hists[i] = hists[i] .symmetric_difference(&hists[rank]) .copied() .collect::<HashSet<_>>(); } rank += 1; } if let Some(ind) = (0..n).find(|&i| a[i] == 0) { let ans = &hists[ind]; println!("{}", ans.len()); for bi in ans { print!("{} ", bi + 1); } println!(); } else { println!("-1"); } }