Preparando MOJI

Phoenix and Towers

2000ms 262144K

Description:

Phoenix has $$$n$$$ blocks of height $$$h_1, h_2, \dots, h_n$$$, and all $$$h_i$$$ don't exceed some value $$$x$$$. He plans to stack all $$$n$$$ blocks into $$$m$$$ separate towers. The height of a tower is simply the sum of the heights of its blocks. For the towers to look beautiful, no two towers may have a height difference of strictly more than $$$x$$$.

Please help Phoenix build $$$m$$$ towers that look beautiful. Each tower must have at least one block and all blocks must be used.

Input:

The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$x$$$ ($$$1 \le m \le n \le 10^5$$$; $$$1 \le x \le 10^4$$$) — the number of blocks, the number of towers to build, and the maximum acceptable height difference of any two towers, respectively.

The second line of each test case contains $$$n$$$ space-separated integers ($$$1 \le h_i \le x$$$) — the heights of the blocks.

It is guaranteed that the sum of $$$n$$$ over all the test cases will not exceed $$$10^5$$$.

Output:

For each test case, if Phoenix cannot build $$$m$$$ towers that look beautiful, print NO. Otherwise, print YES, followed by $$$n$$$ integers $$$y_1, y_2, \dots, y_n$$$, where $$$y_i$$$ ($$$1 \le y_i \le m$$$) is the index of the tower that the $$$i$$$-th block is placed in.

If there are multiple solutions, print any of them.

Sample Input:

2
5 2 3
1 2 3 1 2
4 3 3
1 1 2 3

Sample Output:

YES
1 1 1 2 2
YES
1 2 2 3

Note:

In the first test case, the first tower has height $$$1+2+3=6$$$ and the second tower has height $$$1+2=3$$$. Their difference is $$$6-3=3$$$ which doesn't exceed $$$x=3$$$, so the towers are beautiful.

In the second test case, the first tower has height $$$1$$$, the second tower has height $$$1+2=3$$$, and the third tower has height $$$3$$$. The maximum height difference of any two towers is $$$3-1=2$$$ which doesn't exceed $$$x=3$$$, so the towers are beautiful.

Informação

Codeforces

Provedor Codeforces

Código CF1515C

Tags

constructive algorithmsdata structuresgreedy

Submetido 0

BOUA! 0

Taxa de BOUA's 0%

Datas 09/05/2023 10:13:34

Relacionados

Nada ainda