結果

問題 No.2895 Zero XOR Subset
ユーザー atcoder8
提出日時 2024-09-20 23:10:00
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 1,271 bytes
コンパイル時間 14,167 ms
コンパイル使用メモリ 390,208 KB
実行使用メモリ 406,896 KB
最終ジャッジ日時 2024-09-20 23:10:23
合計ジャッジ時間 18,537 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::BTreeMap;

use proconio::input;

fn main() {
    let answer = match solve() {
        Some(value) => format!(
            "{}\n{}",
            value.len(),
            value
                .iter()
                .map(|val| val.to_string())
                .collect::<Vec<_>>()
                .join(" ")
        ),
        None => "-1".to_string(),
    };
    println!("{}", answer);
}

fn solve() -> Option<Vec<usize>> {
    input! {
        n: usize,
        aa: [usize; n],
    }

    let mut pool = BTreeMap::from([(0_usize, 0_usize)]);
    for (i, &a) in aa.iter().enumerate() {
        let next_pool = pool
            .iter()
            .map(|(&value, &bits)| (value ^ a, bits | 1 << i))
            .collect::<Vec<_>>();
        for &(next_value, next_bits) in &next_pool {
            if pool.contains_key(&next_value) {
                let ans_bits = pool[&next_value] ^ next_bits;
                return Some(
                    (0_usize..)
                        .take_while(|&i| ans_bits >> i != 0)
                        .filter(|&i| ans_bits >> i & 1 == 1)
                        .map(|i| i + 1)
                        .collect(),
                );
            }
        }

        pool.extend(next_pool);
    }

    None
}
0