結果

問題 No.2895 Zero XOR Subset
ユーザー Yukino DX.
提出日時 2024-10-22 20:39:39
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 28 ms / 2,000 ms
コード長 1,736 bytes
コンパイル時間 15,493 ms
コンパイル使用メモリ 401,308 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2024-10-22 20:39:59
合計ジャッジ時間 19,359 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::HashSet;

use proconio::input;

fn main() {
    input! {
        mut n:usize,
        a:[usize;n],
    }
    const D: usize = 60;

    let n = n.min(100);
    let mut mat = vec![vec![0; D]; n];
    for i in 0..n {
        for j in 0..D {
            if a[i] & (1 << j) != 0 {
                mat[i][j] = 1;
            }
        }
    }

    // show(&mat);
    let mut rank = 0;
    let mut combs = vec![HashSet::new(); n];
    for i in 0..n {
        combs[i].insert(i);
    }
    for j in 0..D {
        let Some(id)=(rank..n).find(|&i|mat[i][j]==1)else{
            continue;
        };
        for jj in 0..D {
            let tmp = mat[rank][jj];
            mat[rank][jj] = mat[id][jj];
            mat[id][jj] = tmp;
        }
        combs.swap(rank, id);

        for i in 0..n {
            if i == rank || mat[i][j] == 0 {
                continue;
            }

            for jj in 0..D {
                mat[i][jj] ^= mat[rank][jj];
            }
            let comb_new = combs[rank].symmetric_difference(&combs[i]);
            combs[i] = comb_new.copied().collect::<HashSet<_>>();
        }

        rank += 1;
        // show(&mat);
        // println!("combs:{:?}", combs)
    }

    if rank == n {
        println!("-1");
        return;
    } else if let Some(row) = (0..n).find(|&i| mat[i].iter().all(|&x| x == 0)) {
        println!("{}", combs[row].len());
        for &id in combs[row].iter() {
            print!("{} ", id + 1);
        }
        println!();
    }
}

#[allow(unused)]
fn show(mat: &Vec<Vec<usize>>) {
    println!("----------");
    for i in 0..mat.len() {
        for j in 0..mat[i].len() {
            print!("{} ", mat[i][j]);
        }
        println!();
    }
}
0