結果
問題 | No.1421 国勢調査 (Hard) |
ユーザー |
![]() |
提出日時 | 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
ソースコード
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());}}}