1957B.md (1754B)
1 Source: https://codeforces.com/problemset/problem/1957/B 2 3 B. A BIT of a Construction 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Given integers $n$ and $k$, construct a sequence of $n$ non-negative (i.e. $\geq 0$) integers $a_1, a_2, \ldots, a_n$ such that 22 23 1. $\sum\limits_{i = 1}^n a_i = k$ 24 2. The number of $1$s in the binary representation of $a_1 | a_2 | \ldots | a_n$ is maximized, where $|$ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR). 25 26 Input 27 28 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 29 30 The only line of each test case contains two integers $n$ and $k$ ($1 \leq n \leq 2 \cdot 10^5$, $1 \leq k \leq 10^9$) — the number of non-negative integers to be printed and the sum respectively. 31 32 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 33 34 Output 35 36 For each test case, output a sequence $a_1, a_2, \ldots, a_n$ on a new line that satisfies the conditions given above. 37 38 If there are multiple solutions, print any of them. 39 40 Example 41 42 Input 43 44 ``` 45 4 46 47 1 5 48 49 2 3 50 51 2 5 52 53 6 51 54 ``` 55 56 Output 57 58 ``` 59 5 60 1 2 61 5 0 62 3 1 1 32 2 12 63 ``` 64 65 Note 66 67 In the first test case, we have to print exactly one integer, hence we can only output $5$ as the answer. 68 69 In the second test case, we output $1, 2$ which sum up to $3$, and $1 | 2 = (11)_2$ has two $1$s in its binary representation, which is the maximum we can achieve in these constraints. 70 71 In the fourth test case, we output $3, 1, 1, 32, 2, 12$ which sum up to $51$, and $3 | 1 | 1 | 32 | 2 | 12 = (101\,111)_2$ has five $1$s in its binary representation, which is the maximum we can achieve in these constraints.