#C5004. Optimized Delivery Distribution

    ID: 48606 Type: Default 1000ms 256MiB

Optimized Delivery Distribution

Optimized Delivery Distribution

You are given the task of distributing a list of orders among n delivery persons such that the maximum total delivery time assigned to any delivery person is minimized. The process of assignment is done as follows:

1. Sort the list of delivery times in descending order.

2. Maintain a min-heap (or priority queue) to keep track of the current total delivery time for each delivery person. Initially, every person has a total delivery time of 0.

3. For each order time in the sorted list, assign the order to the delivery person with the current minimum total delivery time, update that person's total time, and then push them back into the min-heap.

The final output should list the orders assigned to each delivery person in the order they were assigned. Formally, if\( T = [t_1,t_2,\ldots,t_m] \) is the list of order times and persons are numbered from 0 to \( n-1 \), then the algorithm assigns orders such that the updated total times are as balanced as possible.

Note: If a delivery person does not receive any orders, an empty line should be printed for that person.

The assignment strategy can be summarized in the following formula: \[ \text{Let } S_i \text{ be the sum for person } i. \quad \text{At each step, choose } k = \arg\min_i S_i. \quad S_k \gets S_k + t \]

inputFormat

The input is read from standard input (stdin) and consists of two lines:

  1. The first line contains two integers \( n \) and \( m \), where \( n \) is the number of delivery persons and \( m \) is the number of orders.
  2. The second line contains \( m \) space-separated integers representing the delivery times of the orders.

outputFormat

Output to standard output (stdout) exactly \( n \) lines. The \( i\)-th line represents the delivery times assigned to delivery person \( i \) (0-indexed) in the order they were assigned. If a delivery person has no assigned orders, output an empty line.

## sample
3 6
5 2 8 3 7 4
8 2

7 3 5 4

</p>