2161C.md (3721B)
1 Source: https://codeforces.com/problemset/problem/2161/C 2 3 C. Loyalty 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 No Loyalty No Royalty (c) 22 23 You are a customer in a store and want to buy $n$ items. Each item $i$ has a price $a_i$ such that $1 \leq a_i \leq X$, where $X$ is a loyalty factor. 24 25 Your loyalty level in the store is defined as $\lfloor {S \over X} \rfloor$, where $S$ is the total cost of items purchased so far. Initially, $S = 0$. 26 27 If you buy an item with price $p$ and your loyalty level increases as a result of this purchase, you earn $p$ bonus points. 28 29 Your task is to find the maximum number of bonus points you can earn by choosing an optimal order of purchase for the items. 30 31 Input 32 33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2 \cdot 10^4$). The description of the test cases follows. 34 35 The first line of each test case contains two integers $n$ ($1 \leq n \leq 10^5$) and $X$ ($1 \leq X \leq 10^9$) — the number of items and the loyalty factor. 36 37 The second line of each test case contains $n$ integers $a_1$, $a_2$, $\ldots$, $a_n$ ($1 \leq a_i \leq X$) — the prices of the items. 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 40 41 Output 42 43 For each test case, output two lines. 44 45 The first line should contain a single integer — the maximum number of bonus points that can be earned. 46 47 The second line should contain $n$ integers — the prices of the items in an order of purchase that maximizes the number of bonus points. 48 49 If there are several orders that maximize the number of bonus points, you can output any of them. 50 51 Example 52 53 Input 54 55 ``` 56 7 57 58 10 2 59 60 1 2 1 2 1 2 1 2 1 2 61 62 5 10 63 64 2 2 2 2 5 65 66 11 23 67 68 5 5 22 1 21 2 10 3 1 1 2 69 70 1 1 71 72 1 73 74 1 17 75 76 11 77 78 3 100 79 80 44 32 1 81 82 16 100500 83 84 42801 73112 95296 68791 42217 21871 29316 84405 24273 42894 63370 53473 57156 61369 80 27290 85 ``` 86 87 Output 88 89 ``` 90 12 91 1 2 2 2 2 2 1 1 1 1 92 5 93 2 2 2 2 5 94 53 95 1 1 5 2 1 2 5 3 10 21 22 96 1 97 1 98 0 99 11 100 0 101 44 32 1 102 503499 103 53473 42894 80 57156 42801 61369 42217 63370 29316 68791 27290 73112 24273 84405 21871 95296 104 ``` 105 106 Note 107 108 In the first test case: 109 110 1. After buying the first item $S = 1$, loyalty level is 0; 111 2. After buying the second item $S = 3$, this increases loyalty level to $1$ and earns $2$ bonus points; 112 3. After buying the third item $S = 5$, this increases loyalty level to $2$ and earns $2$ bonus points; 113 4. After buying the fourth item $S = 7$, this increases loyalty level to $3$ and earns $2$ bonus points; 114 5. After buying the fifth item $S = 9$, this increases loyalty level to $4$ and earns $2$ bonus points; 115 6. After buying the sixth item $S = 11$, this increases loyalty level to $5$ and earns $2$ bonus points; 116 7. After buying the seventh item $S = 12$, this increases loyalty level to $6$ and earns $1$ bonus point; 117 8. After buying the eighth item $S = 13$; 118 9. After buying the ninth item $S = 14$, this increases loyalty level to $7$ and earns $1$ bonus point; 119 10. After buying the tenth item $S = 15$. 120 121 Overall we got $12$ bonus points. 122 123 In the second test case: 124 125 1. After buying the first four items $S = 8$, loyalty level is 0; 126 2. After buying the last item $S = 13$, this increases loyalty level to $1$ and earns $5$ bonus points. 127 128 In the third test case: 129 130 1. After buying the first eight items $S = 20$, loyalty level is 0; 131 2. After buying the ninth item $S = 30$, this increases loyalty level to $1$ and earns $10$ bonus points; 132 3. After buying the tenth item $S = 51$, this increases loyalty level to $2$ and earns $21$ bonus points; 133 4. After buying the eleventh item $S = 73$, this increases loyalty level to $3$ and earns $22$ bonus points.