Submission #74118342

---

Source Code Expand

use proconio::input;

fn main() {
    input! {
        n: usize,
        m: usize,
        a: [usize; n],
        q: usize,
        x: [u128; q],
    }

    let mut count = vec![0usize; m + 1];
    for &val in &a {
        count[val] += 1;
    }

    let max_possible_count = n + m + 1;
    let mut by_count: Vec<Vec<usize>> = vec![Vec::new(); max_possible_count];
    for v in 1..=m {
        by_count[count[v]].push(v);
    }

    let mut added: Vec<usize> = Vec::with_capacity(m * 2);
    let mut min_count = 0;
    while min_count < max_possible_count && by_count[min_count].is_empty() {
        min_count += 1;
    }

    loop {
        let mut max_count = min_count;
        for c in (min_count + 1)..max_possible_count {
            if !by_count[c].is_empty() {
                max_count = c;
            }
        }

        if min_count == max_count {
            break;
        }

        let values = std::mem::take(&mut by_count[min_count]);
        if values.is_empty() {
            while min_count < max_possible_count && by_count[min_count].is_empty() {
                min_count += 1;
            }
            if min_count >= max_possible_count {
                break;
            }
            continue;
        }

        for v in values {
            added.push(v);
            count[v] += 1;
            by_count[count[v]].push(v);
        }

        while min_count < max_possible_count && by_count[min_count].is_empty() {
            min_count += 1;
        }
        if min_count >= max_possible_count {
            break;
        }
    }

    let total_added = added.len();

    for &xi in &x {
        if xi <= n as u128 {
            println!("{}", a[(xi - 1) as usize]);
        } else {
            let pos = xi - n as u128;
            if pos <= total_added as u128 {
                println!("{}", added[(pos - 1) as usize]);
            } else {
                let remaining = pos - total_added as u128;
                let val = ((remaining - 1) % m as u128) as usize + 1;
                println!("{}", val);
            }
        }
    }
}

Submission Info

Judge Result