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 index: usize = 0;
    while k < m {
        let previous_part_count = sticks[index].parts.len() as u32;
        let denominator = previous_part_count + 1;
        let new_parts = divide_stick(sticks[index].length, denominator);
        assert!(new_parts[0] <= max.0);
        let old_parts = &sticks[index].parts;
        let required_cuts = new_parts.len() - old_parts.len();
        assert!(required_cuts <= 1);

        if required_cuts > 0 {
            sticks[index].parts = new_parts;

            // Change max if needed
            if index == max.1 {
                max = (sticks[0].parts[0], 0);
                for i in 1..sticks.len() {
                    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);
            }

            index = max.1;
        } else {
            break;
        }
    }

    assert_eq!(m as usize, answers.len());

    let answers: Vec<String> = answers.iter().take(m as usize).map(|a| a.to_string()).collect();
    println!("{}", answers.join(" "))
}

/// 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);
        }
    }

    assert_eq!(parts.iter().sum::<u32>(), length);
    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: ACCEPTED

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: ACCEPTED

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: ACCEPTED

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