B - |{floor(A_i/2^k)}| Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

正整数 N,K が与えられます。

長さ N で全ての要素が 1 以上 2^K 未満である整数列を 良い数列 と呼びます。

良い数列 A=(A_1,A_2,\ldots,A_N) の スコア を以下のように定義します。

  • 1 以上 N 以下の整数 i と 0 以上の整数 k を用いて \displaystyle \left\lfloor\frac{A_i}{2^k} \right\rfloor と表すことができる整数の個数。

例えば A=(3,5) に対して \displaystyle \left\lfloor\frac{A_i}{2^k} \right\rfloor と表すことができる整数は 0,1,2,3,5 の 5 個なのでスコアは 5 となります。

良い数列でスコアを最大にするものを一つ求めてください。

T 個のテストケースが与えられるので、それぞれについて解いてください。

制約

  • 1\le T\le 10^5
  • 1\le N\le 10^5
  • 1\le K\le 30
  • 全てのテストケースにおける N の総和は 2\times 10^5 以下である
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ここで、 \mathrm{case}_i は i 番目のテストケースを意味する。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる。

N K

出力

T 行出力せよ。

i 行目には \mathrm{case}_i に対するスコアを最大化する良い数列を一つ出力せよ。

なお、スコアを最大化する良い数列が複数存在する場合は、どれを出力しても正答となる。

入力例 1

3
3 3
7 2
8 20

出力例 1

5 6 7
2 2 3 3 1 3 3
662933 967505 876482 840117 1035841 651549 543175 781219

1 つ目のテストケースについて考えます。

A=(5,6,7) とすると、\displaystyle \left\lfloor\frac{A_i}{2^k} \right\rfloor という形で表せる整数は 0,1,2,3,5,6,7 の 7 個なので、この良い数列のスコアは 7 です。

A=(7,4,5) や A=(6,5,4) などを出力しても正解となります。

Score : 500 points

Problem Statement

You are given positive integers N and K.

An integer sequence of length N where all elements are between 1 and 2^K - 1, inclusive, is called a good sequence.

The score of a good sequence A=(A_1,A_2,\ldots,A_N) is defined as follows:

  • The number of distinct integers that can be expressed as \displaystyle \left\lfloor\frac{A_i}{2^k} \right\rfloor using an integer i between 1 and N, inclusive, and a non-negative integer k.

For example, for A=(3,5), five integers can be expressed as \displaystyle \left\lfloor\frac{A_i}{2^k} \right\rfloor: 0, 1, 2, 3, and 5, so the score is 5.

Find one good sequence with the maximum score.

For each input file, you are given T test cases to solve.

Constraints

  • 1 \leq T \leq 10^5
  • 1 \leq N \leq 10^5
  • 1 \leq K \leq 30
  • The sum of N across the test cases in a single input file is at most 2 \times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format. Here, \text{case}_i denotes the i-th test case.

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N K

Output

Print T lines.

The i-th line should contain the answer for \mathrm{case}_i.

If there are multiple good sequences with the maximum score, any of them will be accepted.

Sample Input 1

3
3 3
7 2
8 20

Sample Output 1

5 6 7
2 2 3 3 1 3 3
662933 967505 876482 840117 1035841 651549 543175 781219

Consider the first test case.

For A=(5,6,7), seven integers can be expressed as \displaystyle \left\lfloor\frac{A_i}{2^k} \right\rfloor: 0, 1, 2, 3, 5, 6, and 7, so its score is 7.

Outputs such as A=(7,4,5) and A=(6,5,4) would also be accepted.