結果

問題 No.1421 国勢調査 (Hard)
ユーザー 57tggx57tggx
提出日時 2021-01-27 08:49:05
言語 Rust
(1.77.0 + proconio)
結果
WA  
実行時間 -
コード長 4,965 bytes
コンパイル時間 15,739 ms
コンパイル使用メモリ 381,176 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-27 03:01:06
合計ジャッジ時間 19,327 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: the item `TryInto` is imported redundantly
   --> src/main.rs:135:17
    |
135 |             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

ソースコード

diff # 

// スペシャルジャッジが正しければ，
// このコードは全ケース WA になります．

fn main() {
    let input = Input::read();

    assert!(matches!(input.n, 1..=50));
    assert!(matches!(input.m, 1..=100_000));
    for (a, b, y) in &input.t {
        assert!(1 <= *a && *a <= input.n);
        {
            let mut prev = None;
            for i in b {
                assert!(prev < Some(*i), "{:?}", b);
                prev = Some(*i);
            }
        }
        assert!(matches!(y, 0..=0x3fffffff));
    }

    let mut map = ReduceMap::new(input.n);
    // map.print();
    let mut flag = false;
    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) {
            flag = true;
            // println!("-1");
            // return;
        }
        // map.print();
    }
    // map.print();
    if flag {
        let ans = map.construct();
        for &i in &ans {
            println!("{}", i);
        }
    } else {
        println!("-1");
    }
}

#[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