1 unstable release

0.1.0 Jun 27, 2019

#846 in Data structures

Download history 46/week @ 2021-02-25 44/week @ 2021-03-04 38/week @ 2021-03-11 57/week @ 2021-03-18 74/week @ 2021-03-25 80/week @ 2021-04-01 55/week @ 2021-04-08 69/week @ 2021-04-15 48/week @ 2021-04-22 88/week @ 2021-04-29 42/week @ 2021-05-06 46/week @ 2021-05-13 53/week @ 2021-05-20 64/week @ 2021-05-27 49/week @ 2021-06-03 53/week @ 2021-06-10

244 downloads per month
Used in 3 crates

MIT license

13KB
378 lines

bitset-fixed

Bitset for DP.

Example

Example for AGC20-C

use bitset_fixed::BitSet;
use rand::prelude::*;

fn main() {
    let mut rng = StdRng::seed_from_u64(114514);

    let n: Vec<usize> = (0..25).map(|_| rng.next_u32() as usize % 2000).collect();
    let sum = n.iter().sum::<usize>();

    let mut bitset = BitSet::new(sum + 1);
    bitset.set(0, true);

    for &x in &n {
        bitset |= &(&bitset << x);
    }

    let ans = ((sum + 1) / 2..).find(|&i| bitset[i]).unwrap();

    println!("N = {:?}\nAnswer = {}", n, ans);
}

No runtime deps