competitive/algorithm/
other.rs

1#[codesnip::entry]
2/// return: \[(elem, length)\]
3pub fn run_length_encoding<T, I>(iter: I) -> Vec<(T, usize)>
4where
5    T: Clone + PartialEq,
6    I: IntoIterator<Item = T>,
7{
8    let mut res = Vec::new();
9    for a in iter.into_iter() {
10        if let Some((p, len)) = res.last_mut() {
11            if p == &a {
12                *len += 1;
13                continue;
14            }
15        }
16        res.push((a, 1));
17    }
18    res
19}
20
21#[codesnip::entry]
22/// $y = \left\lfloor\frac{n}{x}\right\rfloor$
23///
24/// segments that have same x or y
25pub fn floor_kernel(n: usize) -> Vec<usize> {
26    let m = (n as f64).sqrt() as usize;
27    let mut res = Vec::with_capacity(m * 2 + 1);
28    for i in 1..=m {
29        res.push(i);
30    }
31    if n / m + 1 != m + 1 {
32        res.push(m + 1);
33    }
34    for i in (1..=m).rev() {
35        res.push(n / i + 1);
36    }
37    res
38}
39
40#[cfg(test)]
41mod tests {
42    use super::*;
43    use crate::{rand, tools::Xorshift};
44
45    #[test]
46    fn test_run_length_encoding() {
47        let mut rng = Xorshift::default();
48        const N: usize = 100_000;
49        rand!(rng, v: [0u8..8u8; N]);
50        let r = run_length_encoding(v.iter());
51        let mut s = 0;
52        for (a, l) in r {
53            for v in &v[s..s + l] {
54                assert_eq!(a, v);
55            }
56            s += l;
57        }
58    }
59
60    #[test]
61    fn test_floor_kernel() {
62        for n in 1..1000 {
63            let k = floor_kernel(n);
64            let from = k.iter().cloned().zip(k.iter().cloned().skip(1));
65            let to = k.iter().cloned().zip(k.iter().cloned().skip(1)).rev();
66            for ((a, b), (c, d)) in from.zip(to) {
67                assert!(a < b);
68                assert!(c < d);
69                for x in a..b {
70                    for y in c..d {
71                        assert!(x * y <= n);
72                    }
73                }
74            }
75        }
76    }
77}
competitive/algorithm/other.rs

competitive/algorithm/
other.rs
