Tikut

use std::io;
 
struct Stick {
    length: u32, // Original length. Shall never be modified.
    parts: Vec<u32> // Lengths of each part. Should always be in descending order.
}
 
fn main() {
    let stdin = io::stdin();
 
    let (n, m) = {
        let mut input: String = String::new();
        stdin.read_line(&mut input).unwrap();
        let mut iter = input.trim().split_whitespace().map(|x| x.parse::<u32>().unwrap());
        (iter.next().unwrap(), iter.next().unwrap())
    };
 
    let mut sticks: Vec<Stick> = {
        let mut input: String = String::new();
        stdin.read_line(&mut input).unwrap();
        input.trim().split_whitespace().map(|x| {
            let length = x.parse::<u32>().unwrap();
            Stick {
                length,
                parts: vec![length]
            }
        }).collect()
    };
    assert_eq!(sticks.len(), n as usize);
 
    sticks.sort_by(|a, b| b.length.cmp(&a.length));
    let original_max = sticks.first().unwrap().length;
    let original_min = sticks.last().unwrap().length;
    let mut max = (original_max, 0);
    let mut min = (original_min, sticks.len() - 1);
    
    let mut answers = Vec::<u32>::with_capacity(m as usize);
 
    let mut k = 0;
    let mut prev_k: u32 = k;
    let mut index: usize = 0;
    let mut denominator: u32 = 2;
    while k < m {
        let split = should_stick_be_split(sticks[index].length, denominator, &original_max);
        if split {
            let previous_part_count = sticks[index].parts.len() as u32;
            for inner_denominator in (previous_part_count + 1)..=denominator {
                if k >= m {
                    break;
                }
 
                let new_parts = divide_stick(sticks[index].length, inner_denominator);
                debug_assert!(new_parts[0] <= max.0);
                assert_eq!(new_parts.len() - &sticks[index].parts.len(), 1);
 
                sticks[index].parts = new_parts;
 
                // Change max if needed
                if index == max.1 {
                    max.0 = sticks[index].parts[0];
                    for i in (index..sticks.len()).chain([0]) {
                        if sticks[i].parts[0] > max.0 {
                            max = (sticks[i].parts[0], i);
                        }
                    }
                }
 
                // Change min if needed
                if sticks[index].parts.last().unwrap() < &min.0 {
                    min = (*sticks[index].parts.last().unwrap(), index);
                }
 
                k += 1;
                answers.push(max.0 - min.0);
 
                {
                    let mut calculated_max = *sticks.first().unwrap().parts.first().unwrap();
                    let mut calculated_min = *sticks.last().unwrap().parts.last().unwrap();
                    for stick in &sticks {
                        for part in &stick.parts {
                            if *part < calculated_min {
                                calculated_min = *part;
                            }
                            if *part > calculated_max {
                                calculated_max = *part;
                            }
                        }
                    }
                    assert_eq!(calculated_min, min.0);
                    assert_eq!(calculated_max, max.0);
                }
            }
        }
 
        if split && sticks.len() > index + 1 {
            index += 1;
        } else {
            if prev_k == k {
                break;
            }
            prev_k = k;
            denominator += 1;
            index = 0;
        }
    }
 
    let answers: Vec<String> = answers.iter().take(m as usize).map(|a| a.to_string()).collect();
    println!("{}", answers.join(" "))
}
 
 
fn should_stick_be_split(stick_length: u32, denominator: u32, original_max: &u32) -> bool {
    if stick_length < denominator {
        false
    } else {
        let last_useful_length = original_max / denominator + if original_max % denominator == 0 { 0 } else { 1 };
        stick_length >= last_useful_length
    }
 
}
 
/// Divides a stick of given length into `denominator` parts.
/// The returned Vec is in descending size order. max - min <= 1 inside the Vec.
fn divide_stick(length: u32, denominator: u32) -> Vec<u32> {
    let mut parts = Vec::with_capacity(denominator as usize);
 
    let div = length / denominator;
    if div > 0 {
        let mut extra = length % denominator;
        for _ in 0..denominator {
            if extra > 0 {
                extra -= 1;
                parts.push(div + 1);
            } else {
                parts.push(div);
                assert!(div > 0);
            }
        }
    } else {
        for _ in 0..length {
            parts.push(1);
        }
    }
 
    debug_assert_eq!(parts.iter().sum::<u32>(), length);
    debug_assert!(parts.iter().max().unwrap() - parts.iter().min().unwrap() <= 1);
    parts
}

Test 1

Group: 1, 3, 4, 5, 6

Verdict: ACCEPTED

Test 2

Group: 1, 4, 5, 6

Verdict: WRONG ANSWER

Test 3

Group: 1, 4, 5, 6

Verdict: WRONG ANSWER

Test 4

Group: 1, 4, 5, 6

Verdict: WRONG ANSWER

Test 5

Group: 2, 5, 6

Verdict: ACCEPTED

Test 6

Group: 2, 5, 6

Verdict: ACCEPTED

Test 7

Group: 3, 5, 6

Verdict: ACCEPTED

Test 8

Group: 3, 5, 6

Verdict: ACCEPTED

Test 9

Group: 3, 5, 6

Verdict: ACCEPTED

Test 10

Group: 3, 5, 6

Verdict: ACCEPTED

Test 11

Group: 3, 5, 6

Verdict: WRONG ANSWER

Test 12

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 13

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 14

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 15

Group: 4, 5, 6

Verdict: WRONG ANSWER

Test 16

Group: 5, 6

Verdict: WRONG ANSWER

Test 17

Group: 5, 6

Verdict: WRONG ANSWER

Test 18

Group: 5, 6

Verdict: WRONG ANSWER

Test 19

Group: 5, 6

Verdict: WRONG ANSWER

Test 20

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 6

Verdict: TIME LIMIT EXCEEDED