結果

問題 No.2895 Zero XOR Subset
ユーザー Yukino DX.Yukino DX.
提出日時 2024-10-22 20:39:39
言語 Rust
(1.77.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,824 KB
testcase_02 AC 28 ms
7,296 KB
testcase_03 AC 4 ms
6,816 KB
testcase_04 AC 5 ms
6,820 KB
testcase_05 AC 4 ms
6,816 KB
testcase_06 AC 27 ms
7,296 KB
testcase_07 AC 4 ms
6,820 KB
testcase_08 AC 28 ms
7,424 KB
testcase_09 AC 4 ms
6,824 KB
testcase_10 AC 3 ms
6,820 KB
testcase_11 AC 4 ms
6,824 KB
testcase_12 AC 28 ms
7,296 KB
testcase_13 AC 5 ms
6,820 KB
testcase_14 AC 4 ms
6,816 KB
testcase_15 AC 28 ms
7,296 KB
testcase_16 AC 4 ms
6,820 KB
testcase_17 AC 4 ms
6,820 KB
testcase_18 AC 27 ms
7,424 KB
testcase_19 AC 5 ms
6,820 KB
testcase_20 AC 3 ms
6,816 KB
testcase_21 AC 4 ms
6,824 KB
testcase_22 AC 4 ms
6,816 KB
testcase_23 AC 4 ms
6,820 KB
testcase_24 AC 4 ms
6,820 KB
testcase_25 AC 4 ms
6,820 KB
testcase_26 AC 27 ms
7,296 KB
testcase_27 AC 4 ms
6,820 KB
testcase_28 AC 4 ms
6,820 KB
testcase_29 AC 27 ms
7,296 KB
testcase_30 AC 5 ms
6,816 KB
testcase_31 AC 5 ms
6,820 KB
testcase_32 AC 27 ms
7,296 KB
testcase_33 AC 4 ms
6,820 KB
testcase_34 AC 28 ms
7,296 KB
testcase_35 AC 4 ms
6,816 KB
testcase_36 AC 28 ms
7,296 KB
権限があれば一括ダウンロードができます

ソースコード

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