Submission #39658094

---

Source Code Expand

// -*- coding:utf-8-unix -*-
pub fn main() {
    proconio::input! {
        h: usize, w: usize,
        a: [u32; w * h],
    }

    let mut comp_hash = rustc_hash::FxHashMap::with_capacity_and_hasher(w * h, std::hash::BuildHasherDefault::default());
    let mut comp_count = 0usize;
    let a: Vec<usize> = std::iter::FromIterator::from_iter(a.iter().map(|&e| *comp_hash.entry(e).or_insert_with(|| { let c = comp_count; comp_count += 1; c }) ));

    let h1 = h - 1;
    let w1 = w - 1;
    let hw2 = h1 + w1;

    let mut count = 0usize;

    let mut hset = rustc_hash::FxHashSet::<u32>::default();
    let mut comb = (1u32 << w1) - 1;
    while comb < (1 << hw2) {
        let mut hbool = [false; 100];
        hset.clear();
        let mut i = 0;
        count += 1;
        for k in 0..hw2 {
            hbool[a[i]] = true;
            i += if comb & (1 << k) == 0 { w } else { 1 };
            if hbool[a[i]] {
                count -= 1;
                break;
            }
        }
        let x = comb & comb.wrapping_neg();
        let y = comb + x;
        comb = ((comb & !y) / x >> 1) | y;
    }

    println!("{}", count);
}

Submission Info

Judge Result