#482323 (Rust) No.1056 2D Lamps

• 問題: No.1056 2D Lamps
• ユーザー: akakimidori
• 提出日時: 2020-05-15 22:56:47
• 言語: Rust (1.83.0 + proconio)
• 結果: TLE
• 実行時間: -
• コード長: 8,606 bytes
• コンパイル時間: 12,319 ms
• コンパイル使用メモリ: 378,568 KB
• 実行使用メモリ: 48,384 KB
• 最終ジャッジ日時: 2024-09-19 12:21:54
• 合計ジャッジ時間: 17,528 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	AC * 3
other	TLE * 1 -- * 13

ソースコード

// ---------- begin BitSet ----------
#[derive(Clone)]
struct BitSet {
    size: usize,
    a: Vec<usize>,
}

fn bit_size() -> usize {
    8 * std::mem::size_of::<usize>()
}

fn quot_rem(n: usize) -> (usize, usize) {
    let w = bit_size();
    (n / w, n % w)
}

#[allow(dead_code)]
impl BitSet {
    fn new(size: usize) -> Self {
        let w = bit_size();
        BitSet {
            size: size,
            a: vec![0; (size + w - 1) / w],
        }
    }
    fn set_at(&mut self, x: usize) {
        assert!(x < self.size);
        let (q, r) = quot_rem(x);
        self.a[q] |= 1 << r;
    }
    fn clear_at(&mut self, x: usize) {
        assert!(x < self.size);
        let (q, r) = quot_rem(x);
        self.a[q] &= !(1 << r);
    }
    fn get_at(&self, x: usize) -> bool {
        if x >= self.size {
            return false;
        }
        let (q, r) = quot_rem(x);
        (self.a[q] >> r) & 1 == 1
    }
    fn any(&self) -> bool {
        self.a.iter().any(|a| *a != 0)
    }
    fn fix(&mut self) {
        let (q, r) = quot_rem(self.size);
        if r != 0 {
            self.a[q] &= (1 << r) - 1;
        }
    }
    fn clear(&mut self) {
        let len = self.a.len();
        self.a.clear();
        self.a.resize(len, 0);
    }
    fn truncate(&mut self, len: usize) {
        if len >= self.size {
            return;
        }
        let w = bit_size();
        self.a.truncate((len + w - 1) / w);
        self.size = len;
        self.fix();
    }
    fn popcnt(&self) -> usize {
        self.a.iter().fold(0, |s, a| s + a.count_ones() as usize)
    }
    fn shift_left(&self, rhs: usize) -> Self {
        let (q, r) = quot_rem(rhs);
        let mut ans = BitSet::new(self.size + rhs);
        if r == 0 {
            for (x, y) in ans.a[q..].iter_mut().zip(self.a.iter()) {
                *x = *y;
            }
        } else {
            let w = bit_size();
            let mut prev = 0;
            for (x, y) in ans.a[q..].iter_mut().zip(self.a.iter()) {
                *x = (*y << r) | (prev >> (w - r));
                prev = *y;
            }
            *ans.a.last_mut().unwrap() |= prev >> (w - r);
        }
        ans.fix();
        ans
    }
    fn shift_right(&self, rhs: usize) -> Self {
        if rhs >= self.size {
            return BitSet::new(1);
        }
        let (q, r) = quot_rem(rhs);
        let mut ans = BitSet::new(self.size - rhs);
        if r == 0 {
            for (x, y) in ans.a.iter_mut().zip(self.a[q..].iter()) {
                *x = *y;
            }
        } else {
            let w = bit_size();
            let mut prev = 0;
            for (x, y) in ans.a.iter_mut().zip(self.a[q..].iter()).rev() {
                *x |= (*y >> r) | (prev << (w - r));
                prev = *y;
            }
        }
        ans.fix();
        ans
    }
    fn bitwise_or(&self, rhs: &Self) -> Self {
        let (x, y) = if self.size >= rhs.size {(self, rhs)} else {(rhs, self)};
        let mut a = x.a.clone();
        for (a, y) in a.iter_mut().zip(y.a.iter()) {
            *a |= *y;
        }
        BitSet {
            size: x.size,
            a: a,
        }
    }
    fn bitwise_and(&self, rhs: &Self) -> Self {
        let (x, y) = if self.size <= rhs.size {(self, rhs)} else {(rhs, self)};
        let mut a = x.a.clone();
        for (a, y) in a.iter_mut().zip(y.a.iter()) {
            *a &= *y;
        }
        BitSet {
            size: x.size,
            a: a,
        }
    }
    fn bitwise_xor(&self, rhs: &Self) -> Self {
        let (x, y) = if self.size >= rhs.size {(self, rhs)} else {(rhs, self)};
        let mut a = x.a.clone();
        for (a, y) in a.iter_mut().zip(y.a.iter()) {
            *a ^= *y;
        }
        BitSet {
            size: x.size,
            a: a,
        }
    }
    fn bitwise_or_assign(&mut self, rhs: &Self) {
        if self.size < rhs.size {
            self.size = rhs.size;
            self.a.resize(rhs.a.len(), 0);
        }
        for (a, b) in self.a.iter_mut().zip(rhs.a.iter()) {
            *a |= *b;
        }
    }
    fn bitwise_and_assign(&mut self, rhs: &Self) {
        if self.size > rhs.size {
            self.size = rhs.size;
            self.a.resize(rhs.a.len(), 0);
        }
        for (a, b) in self.a.iter_mut().zip(rhs.a.iter()) {
            *a &= *b;
        }
    }
    fn bitwise_xor_assign(&mut self, rhs: &Self) {
        if self.size < rhs.size {
            self.size = rhs.size;
            self.a.resize(rhs.a.len(), 0);
        }
        for (a, b) in self.a.iter_mut().zip(rhs.a.iter()) {
            *a ^= *b;
        }
    }
    fn trailing_zeros(&self) -> usize {
        let mut ans = 0;
        for a in self.a.iter() {
            if *a != 0 {
                ans += a.trailing_zeros() as usize;
                break;
            } else {
                ans += bit_size();
            }
        }
        ans
    }
}
// ---------- end BitSet ----------
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

//

fn run() {
    input! {
        n: usize,
        m: usize,
        board: [[chars; n]; m],
    }
    let len = n * n;
    let board: Vec<BitSet> = board.into_iter().map(|b| {
        let mut bit = BitSet::new(len);
        for (i, b) in b.into_iter().enumerate() {
            for (j, c) in b.into_iter().enumerate() {
                if c == '#' {
                    bit.set_at(i * n + j);
                }
            }
        }
        bit
    }).collect();
    let mut base = vec![];
    for i in 0..n {
        let mut bit = BitSet::new(len);
        for j in 0..n {
            bit.set_at(i * n + j);
        }
        base.push(bit);
    }
    for j in 0..n {
        let mut bit = BitSet::new(len);
        for i in 0..n {
            bit.set_at(i * n + j);
        }
        base.push(bit);
    }
    for k in 0..(2 * n - 1) {
        let mut bit = BitSet::new(len);
        for i in 0..=k {
            let j = k - i;
            if i < n && j < n {
                bit.set_at(i * n + j);
            }
        }
        base.push(bit);
    }
    for k in 0..(2 * n - 1) {
        let mut bit = BitSet::new(len);
        let mut x = n;
        let mut y = k + 1;
        while x > 0 && y > 0 {
            x -= 1;
            y -= 1;
            if x < n && y < n {
                bit.set_at(x * n + y);
            }
        }
        base.push(bit);
    }
    let mut b = base;
    let mut base = vec![];
    while b.len() > 0 {
        let k = b.iter().map(|b| b.trailing_zeros()).enumerate().min_by_key(|p| p.1).unwrap().0;
        let v = b.remove(k);
        let k = v.trailing_zeros();
        if k >= len {
            break;
        }
        for b in b.iter_mut() {
            if b.trailing_zeros() == k {
                b.bitwise_xor_assign(&v);
            }
        }
        base.push(v);
    }
    let mut ans = String::new();
    for i in 0..(m - 1) {
        for j in (i + 1)..m {
            let mut bit = board[i].bitwise_xor(&board[j]);
            let mut k = bit.trailing_zeros();
            for b in base.iter() {
                if k == b.trailing_zeros() {
                    bit.bitwise_xor_assign(b);
                    k = bit.trailing_zeros();
                }
            }
            if k >= len {
                ans.push('1');
            } else {
                ans.push('0');
            }
        }
        ans.push('\n');
    }
    print!("{}", ans);
}

fn main() {
    run();
}