QOJ.ac

QOJ

Time Limit: 2.0 s Memory Limit: 2048 MB

#22847. 尋找遞增子序列

Statistics

給定一個正整數 $N$ 與一個非負整數 $X$。

請判斷是否存在一個長度為 $2N$ 的序列 $A = (A_1, A_2, \dots, A_{2N})$,同時滿足以下所有條件:

  • 從 $1$ 到 $N$ 的每個整數在 $A$ 中恰好出現兩次。
  • 序列 $(1, 2, \dots, N)$ 作為 $A$ 的子序列恰好出現 $X$ 次。換句話說,恰好有 $X$ 種選擇下標 $1 \le i_1 < i_2 < \dots < i_N \le 2N$ 的方法,使得 $A_{i_j} = j$ $(1 \le j \le N)$。

若存在這樣的序列,請輸出其中一個。若存在多個滿足條件的序列,輸出任意一個即可。

輸入格式

輸入包含多組測試資料,格式如下:

$$ \begin{aligned} &T \\ &\mathrm{case}_1 \\ &\mathrm{case}_2 \\ &\vdots \\ &\mathrm{case}_T \end{aligned} $$

每組測試資料的格式如下:

$$ N \ X $$

第一行包含一個整數 $T$ $(1 \le T \le 2 \times 10^5)$,代表測試資料的組數。

對於每組測試資料,給定一個正整數 $N$ $(1 \le N \le 2 \times 10^5)$ 與一個非負整數 $X$ $(0 \le X \le 10^{18})$。

所有測試資料中 $N$ 的總和不會超過 $2 \times 10^5$。

輸出格式

對於每組測試資料,若不存在滿足條件的序列,請在單獨一行輸出 No。

否則,在第一行輸出 Yes,並在第二行輸出 $2N$ 個整數 $A_1, A_2, \dots, A_{2N}$,代表一個滿足條件的序列。

若有多個合法的序列,輸出其中任意一個皆可。

範例

輸入格式 1

3
2 3
50 1000000000000000000
4 0

輸出格式 1

Yes
1 2 1 2
No
Yes
4 4 3 3 2 2 1 1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.