Ruudukko

warning: unused import: `std::collections::BTreeSet`
 --> input/code.rs:1:5
  |
1 | use std::collections::BTreeSet;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `std::collections::HashSet`
 --> input/code.rs:2:5
  |
2 | use std::collections::HashSet;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^

use std::collections::BTreeSet;
use std::collections::HashSet;
use std::io::BufRead;
use std::str::FromStr;

#[derive(Clone)]
struct Bitset(Vec<u64>);

impl Bitset {
    fn with_size(n: usize) -> Self {
        Self(vec![0; (n + 63) / 64])
    }

    fn union(&mut self, other: &Self) {
        while self.0.len() < other.0.len() {
            self.0.push(0);
        }
        let n = self.0.len().min(other.0.len());
        for i in 0..n {
            self.0[i] |= other.0[i];
        }
    }

    fn set(&mut self, i: usize) {
        let inner = i % 64;
        let outer = i / 64;
        while self.0.len() < outer + 1 {
            self.0.push(0);
        }
        self.0[outer] |= 1u64 << inner;
    }

    fn shift_left(&mut self, n: usize) {
        let inner = n % 64;
        let outer = n / 64;
        for _ in 0..outer + 1 {
            self.0.push(0);
        }

        for leg in (outer + 1..self.0.len()).rev() {
            self.0[leg] =
                (self.0[leg - outer] << inner) | (self.0[leg - outer - 1] >> (64 - inner));
        }
        self.0[outer] = self.0[0] << inner;

        while let Some(0) = self.0.last() {
            self.0.pop();
        }
    }

    fn count(&self) -> usize {
        let mut res = 0usize;
        for i in &self.0 {
            res += i.count_ones() as usize;
        }
        res
    }
}

impl Default for Bitset {
    fn default() -> Self {
        Self::with_size(0)
    }
}

struct Grid<T> {
    data: Vec<T>,
    width: usize,
    height: usize,
}
impl<T> Grid<T> {
    fn new(width: usize, height: usize) -> Self
    where
        T: Default + Copy,
    {
        Self {
            data: vec![Default::default(); width * height],
            width,
            height,
        }
    }
}

impl<T> std::ops::Index<(usize, usize)> for Grid<T> {
    type Output = T;
    fn index(&self, index: (usize, usize)) -> &Self::Output {
        assert!(index.0 < self.width);
        assert!(index.1 < self.height);
        &self.data[self.width * index.1 + index.0]
    }
}

impl<T> std::ops::IndexMut<(usize, usize)> for Grid<T> {
    fn index_mut(&mut self, index: (usize, usize)) -> &mut Self::Output {
        assert!(index.0 < self.width);
        assert!(index.1 < self.height);
        &mut self.data[self.width * index.1 + index.0]
    }
}

fn solve(grid: Grid<bool>) -> usize {
    let n = grid.width;
    let mut possibilities: Vec<Bitset> = Vec::with_capacity(n);
    for _ in 0..n {
        possibilities.push(Default::default());
    }

    // possibilities[0].insert(1);
    possibilities[0].set(0);

    for y in 0..n {
        if grid[(0, y)] {
            // let pos = possibilities[0].iter().map(|v| v + 1).collect();
            possibilities[0].shift_left(1);
        }
        let mut prev = possibilities[0].clone();
        for x in 1..n {
            // let pos = possibilities[x - 1].union(&possibilities[x]);
            // possibilities[x] = if grid[(x, y)] {
            //     pos.map(|v| v + 1).collect()
            // } else {
            //     pos.copied().collect()
            // };
            possibilities[x].union(&prev);
            if grid[(x, y)] {
                possibilities[x].shift_left(1);
            }
            prev = possibilities[x].clone();
        }
    }

    possibilities[n - 1].count()
}

fn main() {
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let mut lines = stdin.lines();
    let n = usize::from_str(&lines.next().unwrap().unwrap()).unwrap();

    let mut grid = Grid::new(n, n);

    for y in 0..n {
        let line = lines.next().unwrap().unwrap();
        for (x, c) in line.char_indices() {
            grid[(x, y)] = c == 'o';
        }
    }

    println!("{}", solve(grid));
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn sample_case() {
        let mut grid = Grid::new(4, 4);
        grid[(1, 2)] = true;
        grid[(2, 0)] = true;
        grid[(3, 2)] = true;
        assert_eq!(solve(grid), 3);
    }

    #[test]
    fn test_bitset() {
        let mut a = Bitset::default();
        a.set(10000);
        a.set(50000);
        let mut b = Bitset::default();
        b.set(10000);
        b.set(10001);
        a.union(&b);
        assert_eq!(a.count(), 3);
        for i in 0..100 {
            a.shift_left(1);
            assert_eq!(a.count(), 3);
        }
    }

    #[test]
    fn test_time() {
        use rand::distributions::{Distribution, Uniform};
        use std::time::{Duration, Instant};

        const ITERS: u32 = 30;
        const SIZE: usize = 1000;

        let mut rng = rand::thread_rng();
        let dist = Uniform::from(0..SIZE);

        let mut time = Duration::from_nanos(1);
        for i in 0..ITERS {
            let mut grid = Grid::new(SIZE, SIZE);

            for i in 0..SIZE {
                grid[(dist.sample(&mut rng), dist.sample(&mut rng))] = true;
            }

            std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);
            let start = Instant::now();
            std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);
            solve(grid);
            std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);
            let stop = Instant::now();
            std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);
            let test_time = (stop - start).as_secs_f64();
            assert!(test_time < 1.0, "Took time {}", test_time);

            time += stop - start;
        }

        let time = (time / ITERS).as_secs_f64();
        assert!(time < 1.0, "Average time {}", time);
    }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

Test 7

Group: 2, 3

Verdict: ACCEPTED

Test 8

Group: 2, 3

Verdict: ACCEPTED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 2, 3

Verdict: ACCEPTED

Test 11

Group: 2, 3

Verdict: ACCEPTED

Test 12

Group: 2, 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED

Test 17

Group: 3

Verdict: ACCEPTED

Test 18

Group: 3

Verdict: ACCEPTED