use rand::Rng;
use std::collections::HashMap;
use std::collections::HashSet;
use std::iter::repeat;
fn main() {
    let N = 100;
    let M = 20;
    let Q = 50;
    let testTime = 5000;
    println!("功能测试开始");
    for i in 0..testTime {
        let n = rand::thread_rng().gen_range(0, N) + 1;
        let m = rand::thread_rng().gen_range(0, M) + 1;
        let mut A = randomMatrix(n, rand::thread_rng().gen_range(0, m) + 1, m);
        let q = rand::thread_rng().gen_range(0, Q) + 1;
        let mut B = randomMatrix(q, rand::thread_rng().gen_range(0, m) + 1, m);
        let ans1 = record1(n, m, q, &mut A, &mut B);
        let ans2 = record2(n, m, q, &mut A, &mut B);
        let mut pass = true;
        for j in 0..q {
            if ans1[j as usize] != ans2[j as usize] {
                pass = false;
                break;
            }
        }
        if !pass {
            println!("出错了!");
            break;
        }
    }
    println!("功能测试结束");
}

// 暴力方法
// 为了验证
fn record1(n: i32, m: i32, q: i32, A: &mut Vec<Vec<i32>>, B: &mut Vec<Vec<i32>>) -> Vec<i32> {
    let mut expUsersMap: HashMap<i32, HashSet<i32>> = HashMap::new();
    for i in 0..m {
        expUsersMap.insert(i, HashSet::new());
    }
    for i in 0..n {
        for exp in A[i as usize].iter() {
            let mut a = expUsersMap.get_mut(exp).unwrap();
            a.insert(i);
        }
    }
    let mut ans: Vec<i32> = repeat(0).take(q as usize).collect();
    let mut help: HashSet<i32> = HashSet::new();
    for i in 0..q {
        help.clear();
        for exp in B[i as usize].iter() {
            for user in expUsersMap.get(exp).unwrap().iter() {
                help.insert(*user);
            }
        }
        ans[i as usize] = help.len() as i32;
    }
    return ans;
}

// 正式方法
fn record2(n: i32, m: i32, q: i32, A: &mut Vec<Vec<i32>>, B: &mut Vec<Vec<i32>>) -> Vec<i32> {
    // n 一共有多少人
    // 任何一个实验，需要几个整数，能表示所有人谁出现谁没出现？
    let parts = (n + 31) / 32;
    // m    0 ~ m -1
    // [i]  [.........]
    let mut bitMap: Vec<Vec<i32>> = repeat(repeat(0).take(parts as usize).collect())
        .take(m as usize)
        .collect();
    for i in 0..n {
        // i 人的编号 : a b c
        for exp in A[i as usize].iter() {
            bitMap[*exp as usize][(i / 32) as usize] |= 1 << (i % 32);
        }
    }
    let mut ans: Vec<i32> = repeat(0).take(q as usize).collect();
    for i in 0..q {
        // i号查询 ： a、c、e，一共有多少去重的人
        // a[0] | c[0] | e[0] -> 几个1
        // a[1] | c[1] | e[1] -> 几个1
        let mut all = 0;
        for j in 0..parts {
            let mut status = 0;
            for exp in B[i as usize].iter() {
                status |= bitMap[*exp as usize][j as usize];
            }
            all += countOnes(status);
        }
        ans[i as usize] = all;
    }
    return ans;
}

// 大厂刷题班，32节，leetcode专题 : https:///problems/number-of-1-bits/
fn countOnes(mut n: i32) -> i32 {
    let mut n2: u32;
    if n < 0 {
        n2 = (u32::MAX as i64 + n as i64 + 1) as u32;
    } else {
        n2 = n as u32;
    }
    let mut n = n2;
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
    n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
    n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
    return n as i32;
}

// 为了测试
fn randomMatrix(n: i32, m: i32, v: i32) -> Vec<Vec<i32>> {
    let mut ans: Vec<Vec<i32>> = repeat(repeat(0).take(m as usize).collect())
        .take(n as usize)
        .collect();
    for i in 0..n {
        for j in 0..m {
            ans[i as usize][j as usize] = rand::thread_rng().gen_range(0, v);
        }
    }
    return ans;
}