結果

問題 No.1421 国勢調査 (Hard)
ユーザー 57tggx57tggx
提出日時 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());
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0