結果

問題 No.1421 国勢調査 (Hard)
コンテスト
ユーザー 57tggx
提出日時 2021-01-27 07:55:46
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 4,333 bytes
コンパイル時間 13,026 ms
コンパイル使用メモリ 389,256 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-27 03:00:36
合計ジャッジ時間 15,493 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: the item `TryInto` is imported redundantly
   --> src/main.rs:111:17
    |
111 |             use std::convert::TryInto;
    |                 ^^^^^^^^^^^^^^^^^^^^^
   --> /tmp/rust-20240322-9800-yefgu1/rustc-1.77.0-src/library/std/src/prelude/mod.rs:129:13
    |
    = note: the item `TryInto` is already defined here
    |
    = note: `#[warn(unused_imports)]` on by default

warning: field `m` is never read
  --> src/main.rs:27:5
   |
25 | struct Input {
   |        ----- field in this struct
26 |     n: usize,
27 |     m: usize,
   |     ^
   |
   = note: `Input` has a derived impl for the trait `Debug`, but this is intentionally ignored during dead code analysis
   = note: `#[warn(dead_code)]` on by default

ソースコード

diff # 

fn main() {
    let input = Input::read();
    let mut map = ReduceMap::new(input.n);
    // map.print();
    for (_, b, y) in &input.t {
        let mut visited = 0;
        for i in b {
            visited |= 1 << i;
        }
        // println!("{:0n$b}", visited, n = input.n);
        if !map.insert(visited, *y) {
            println!("-1");
            return;
        }
        // map.print();
    }
    // map.print();
    let ans = map.construct();
    for &i in &ans {
        println!("{}", i);
    }
}

#[derive(Debug)]
struct Input {
    n: usize,
    m: usize,
    t: Vec<(usize, Vec<usize>, u32)>,
}

struct ReduceMap {
    vec: Vec<(u64, u32)>,
}

impl Input {
    fn read() -> Input {
        let stdin = std::io::stdin();
        let (n, m) = {
            let mut s = String::new();
            stdin.read_line(&mut s).unwrap();
            let (prev, n) = {
                let index = s.find(' ').unwrap();
                let n = s[..index].parse().unwrap();
                (index + 1, n)
            };
            let m = if let Some((index, '\n')) = s.char_indices().last() {
                s[prev..index].parse().unwrap()
            } else {
                panic!();
            };
            (n, m)
        };
        let t = {
            let mut vec = Vec::new();
            for _ in 0..m {
                let a = {
                    let mut s = String::new();
                    stdin.read_line(&mut s).unwrap();
                    if let Some((index, '\n')) = s.char_indices().last() {
                        s[..index].parse().unwrap()
                    } else {
                        panic!();
                    }
                };
                let b = {
                    let mut s = String::new();
                    stdin.read_line(&mut s).unwrap();
                    let mut v = Vec::new();
                    let mut prev = 0;
                    for _ in 0..a - 1 {
                        let index = prev + s[prev..].find(' ').unwrap();
                        v.push(s[prev..index].parse::<usize>().unwrap() - 1);
                        prev = index + 1;
                    }
                    let tmp = if let Some((index, '\n')) = s.char_indices().last() {
                        s[prev..index].parse::<usize>().unwrap()
                    } else {
                        panic!();
                    };
                    v.push(tmp - 1);
                    v
                };
                let y = {
                    let mut s = String::new();
                    stdin.read_line(&mut s).unwrap();
                    if let Some((index, '\n')) = s.char_indices().last() {
                        s[..index].parse().unwrap()
                    } else {
                        panic!();
                    }
                };
                vec.push((a, b, y));
            }
            vec
        };
        assert_eq!(stdin.read_line(&mut String::new()).unwrap(), 0);
        Input { n: n, m: m, t: t }
    }
}

impl ReduceMap {
    fn new(n: usize) -> ReduceMap {
        ReduceMap {
            vec: vec![(0, 0); n],
        }
    }
    fn insert(&mut self, key: u64, value: u32) -> bool {
        if key == 0 {
            value == 0
        } else {
            use std::convert::TryInto;
            let index: usize = key.trailing_zeros().try_into().unwrap();
            let (ref mut k, ref mut v) = self.vec[index];
            if *k == 0 {
                assert_eq!(*v, 0);
                *k = key;
                *v = value;
                true
            } else {
                let key = key ^ *k;
                let value = value ^ *v;
                self.insert(key, value)
            }
        }
    }
    fn construct(&self) -> Vec<u32> {
        let n = self.vec.len();
        let mut ret = vec![0; n];
        for (i, &(k, v)) in self.vec.iter().enumerate().rev() {
            if k != 0 {
                let mut x = v;
                for j in i + 1..n {
                    if k >> j & 1 == 1 {
                        x ^= ret[j];
                    }
                }
                ret[i] = x;
            }
        }
        ret
    }
    #[allow(unused)]
    fn print(&self) {
        for (k, v) in &self.vec {
            println!("{:0n$b}: {:b}", k, v, n = self.vec.len());
        }
    }
}
0