In this explanation, we assume that indices start from \(0\).

First, it is unnecessary to include elements less than \(2^{K-1}\) in \(A\). This is because replacing elements less than \(2^{K-1}\) with their double will result in the same or a higher score. Therefore, we can limit the elements of \(A\) to be between \(2^{K-1}\) and \(2^K-1\).

[1] When \(N \geq 2^{K-1}\)

Since we can include all elements between \(2^{K-1}\) and \(2^K-1\) in \(A\), we can set \(A_i = \max(1, 2^K - 1 - i)\) \((0 \le i < N)\), for example.

[2] When \(N < 2^{K-1}\)

First, let’s consider an upper bound of the score. For \(0 \le x < K\), consider the number of elements that appear as \(\displaystyle \left\lfloor\frac{A_i}{2^k} \right\rfloor\) between \(2^x\) and \(2^{x+1}-1\). For each \(A_i\), there is at most one \(k\) that satisfies \(\displaystyle 2^x \le \left\lfloor\frac{A_i}{2^k} \right\rfloor < 2^{x+1}\), so the number of such elements is at most \(N\). On the other hand, there are only \(2^x\) integers between \(2^x\) and \(2^{x+1}\), so the number of elements that appear in this range is at most \(\min(N, 2^x)\). Therefore, by summing over all \(x\), we find that the score has an upper bound of \(\displaystyle 1 + \sum_{x=0}^{K-1}\min(N, 2^x)\).

This upper bound can always be achieved. Specifically, we can construct \(A\) as follows:

• Set \(A_i\) to the sum of \(2^{K-1}\) and the bit-reversal of \(i\).

“The bit-reversal of \(i\)” means the value obtained by reversing the \((K-1)\)-bit binary representation of \(i\).

For example, if \(K=6\) and \(i=6\), then \(i=00110_{(2)}\), so the bit-reversal of \(i\) is \(01100_{(2)}\), which is \(12\).

By implementing the above, we can solve this problem. The time complexity is \(O(NK)\) due to the bit-reversal calculation being the bottleneck.

Sample Implementation (Python3)

for _ in range(int(input())):
    N, K = map(int, input().split())

    def bit_reversal(x):
        return int(bin(x)[2:].zfill(K - 1)[::-1], 2)

    if N >= 2 ** (K - 1):
        print(*[max(1, 2**K - i - 1) for i in range(N)])
    else:
        print(*[2 ** (K - 1) + bit_reversal(i) for i in range(N)])

Additionally, you can also solve it by constructing from the highest bit downwards. See the implementation example below for details.

Sample Implementation (Python3)

for _ in range(int(input())):
    N, K = map(int, input().split())
    C = [1]
    for _ in range(1, K):
        D = [2 * c for c in C] + [2 * c + 1 for c in C]
        C = D[:N]
    while len(C) < N:
        C.append(1)
    print(*C)