#C10195. Balanced Task Distribution

    ID: 39373 Type: Default 1000ms 256MiB

Balanced Task Distribution

Balanced Task Distribution

You are given n tasks, each associated with a weight, and m team members. Your goal is to assign each task to a team member such that the overall workload is balanced. In other words, the absolute difference between the total weights of tasks assigned to any two team members should be as small as possible. Formally, if W_i denotes the total weight assigned to team member i and wmax is the maximum task weight, then for any two team members i and j, it should hold that

[ |W_i - W_j| \leq w_{max} ]

The tasks are labeled from 1 to n. Follow a greedy strategy by first sorting the tasks in descending order of weight, then repeatedly assign the next task to the team member currently having the minimum total workload. Print the resulting assignment, with each team member's tasks (by original task indices) printed on separate lines.

inputFormat

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

  • The first line contains two integers n and m separated by a space, representing the number of tasks and the number of team members respectively.
  • The second line contains n space-separated integers, where the i-th integer represents the weight of the i-th task.

outputFormat

Output to stdout exactly m lines. The i-th line should contain the indices of the tasks assigned to the i-th team member, separated by a single space. If a team member is not assigned any task, output an empty line for that member.

## sample
5 2
5 3 4 2 6
5 2 4

1 3

</p>