1 unstable release

0.1.0 Jun 27, 2019

#1573 in Data structures

Download history 101/week @ 2023-06-12 352/week @ 2023-06-19 281/week @ 2023-06-26 338/week @ 2023-07-03 373/week @ 2023-07-10 276/week @ 2023-07-17 189/week @ 2023-07-24 129/week @ 2023-07-31 250/week @ 2023-08-07 273/week @ 2023-08-14 152/week @ 2023-08-21 172/week @ 2023-08-28 262/week @ 2023-09-04 180/week @ 2023-09-11 227/week @ 2023-09-18 84/week @ 2023-09-25

770 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