Tikut

use std::{cmp, io};
use std::collections::{HashSet, VecDeque};

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 mut min = (sticks.last().unwrap().length, sticks.len() - 1);
    let mut max_list: VecDeque<(u32, HashSet<usize>)> = { // VecDeque<(len, HashSet<indices>)>
        let mut max_list: VecDeque<(u32, HashSet<usize>)> = VecDeque::with_capacity(sticks.len());
        for i in 0..sticks.len() {
            let stick_max = sticks[i].parts[0];
            if !max_list.is_empty() && max_list[max_list.len() - 1].0 == stick_max {
                let last_index = max_list.len() - 1;
                max_list[last_index].1.insert(i);
            } else {
                max_list.push_back((stick_max, HashSet::from([i])));
            }
        }
        max_list
    };
    
    let mut answers = Vec::<u32>::with_capacity(m as usize);
    let mut k = 0;
    while k < m {
        let index: usize = {
            // Splitting a max length stick is usually a good idea.
            let max_value = max_list[0].0;
            let some_max_occurrence = *max_list[0].1.iter().next().unwrap();
            let (max_stick_split_min, max_stick_split_max) = get_extremes_after_next_cut(&sticks[some_max_occurrence]);
            if max_stick_split_min >= min.0 {
                some_max_occurrence
            } else {
                // If splitting the max stick would cause the min value to drop, check if something better could be done.
                let mut next_index = some_max_occurrence;
                let mut next_delta = {
                    let mut comparison_max = max_value;
                    if max_list[0].1.len() <= 1 && max_list.len() > 1 {
                        comparison_max = cmp::max(max_stick_split_max, max_list[1].0);
                    }
                    comparison_max - max_stick_split_min
                };

                for i in 0..sticks.len() {
                    if i == some_max_occurrence {
                        continue;
                    }
                    let (split_min, _) = get_extremes_after_next_cut(&sticks[i]);
                    let delta = max_value - cmp::min(min.0, split_min);
                    if delta < next_delta {
                        next_delta = delta;
                        next_index = i;
                    }
                    if delta == 0 {
                        break;
                    }
                }

                next_index
            }
        };

        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_list[0].0);
        let old_parts = &sticks[index].parts;
        let required_cuts = new_parts.len() - old_parts.len();
        assert!(required_cuts <= 1);

        if required_cuts > 0 {
            // Change max if needed
            if new_parts[0] != old_parts[0] {
                // Add the maximum length of this stick to max_list after splitting.
                match max_list.binary_search_by_key(&-(new_parts[0] as i32), |pair| -(pair.0 as i32)) {
                    Ok(i) => {
                        max_list[i].1.insert(index);
                    }
                    Err(i) => {
                        max_list.insert(i, (new_parts[0], HashSet::from([index])));
                    }
                };

                // Remove the old maximum length of this stick from max_list prior to the split.
                match max_list.binary_search_by_key(&-(old_parts[0] as i32), |pair| -(pair.0 as i32)) {
                    Ok(i) => {
                        max_list[i].1.remove(&index);
                        if max_list[i].1.is_empty() {
                            max_list.remove(i);
                        }
                    }
                    Err(_) => {
                        panic!("Old maximum value {} of stick {} was not in max_list.", &old_parts[0], index);
                    }
                };
            }

            // Change min if needed
            if new_parts.last().unwrap() < &min.0 {
                min = (*new_parts.last().unwrap(), index);
            }

            sticks[index].parts = new_parts;
            let delta = max_list[0].0 - min.0;
            answers.push(delta);
            k += 1;

            {
                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_list[0].0);
            }
        } else {
            assert_eq!(max_list[0].0, 1);
            assert_eq!(min.0, 1);
            break;
        }
    }

    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
}

/// (min, max)
fn get_extremes_after_next_cut(stick: &Stick) -> (u32, u32) {
    let denominator = stick.parts.len() as u32 + 1;
    let min = cmp::max(stick.length / denominator, 1);
    let max = min + if stick.length % denominator == 0 { 0 } else { 1 };
    (min, max)
}

Test 1

Group: 1, 3, 4, 5, 6

Verdict: ACCEPTED

Test 2

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 3

Group: 1, 4, 5, 6

Verdict: ACCEPTED

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

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

Test 20

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 6

Verdict: TIME LIMIT EXCEEDED