A - Inversions of PQ and QP Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

3 つの整数 N,A,B が与えられます。

(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N), Q=(Q_1,Q_2,\dots,Q_N) であって、

  • (P_{Q_1},P_{Q_2},\dots,P_{Q_N}) の転倒数は A
  • (Q_{P_1},Q_{P_2},\dots,Q_{P_N}) の転倒数は B

となるものが存在するか判定し、存在する場合は一つ構築してください。

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

転倒数とは 数列 R=(R_1,R_2,\dots, R_M) の転倒数とは、整数の組 1 \leq i \lt j \leq M であって R_i \gt R_j を満たすものの個数です。

制約

  • 1\le T\le 2\times 10^5
  • 1 \leq N \leq 2\times 10^5
  • 0 \leq A \leq \frac{N(N-1)}{2}
  • 0 \leq B \leq \frac{N(N-1)}{2}
  • 1 つの入力ファイルに含まれる N の総和は 2\times 10^5 以下
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

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

N A B

出力

\mathrm{case}_1,\mathrm{case}_2,\dots,\mathrm{case}_T に対する答えを順に以下の形式で出力せよ。

条件を満たす順列 P=(P_1,P_2,\dots,P_N), Q=(Q_1,Q_2,\dots,Q_N) が存在する場合、

Yes
P_1 P_2 \dots P_N
Q_1 Q_2 \dots Q_N

と出力せよ。存在しない場合は

No

と出力せよ。

解が複数存在する場合、どれを出力しても正解とみなされる。

入力例 1

3
3 3 1
3 1 2
8 13 11

出力例 1

Yes
1 3 2
2 3 1
No
Yes
2 5 8 4 6 3 7 1
2 1 8 5 3 7 4 6

1 つ目のケースに対する出力例について、(P_{Q_1},P_{Q_2},P_{Q_3})=(3,2,1), (Q_{P_1},Q_{P_2},Q_{P_3})=(2,1,3) です。