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 = sticks[index].length >= get_last_useful_stick_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);
                let old_parts = &sticks[index].parts;

                let required_cuts = new_parts.len() - old_parts.len();
                if required_cuts == 0 {
                    continue;
                } else if required_cuts > 1 {
                    panic!("too many cuts");
                }

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

        if split && sticks.len() > index + 1 {
            index += 1;
        } else {
            if prev_k == k {
                eprintln!("Nothing has been split with denominator {} (k = {}), so this is probably a never ending loop. Breaking out.", denominator, 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 get_last_useful_stick_length(denominator: u32, original_max: &u32) -> u32 {
    original_max / denominator + if original_max % denominator == 0 { 0 } else { 1 }
}

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