問題一覧 > 通常問題

No.1087 転倒数の転倒数

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 14
作問者 : tyawanmusityawanmusi / テスター : QCFiumQCFium
6 ProblemId : 4220 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-06-20 15:30:03

問題文

長さ$M$の整数列$X$において、$f(X)$を次のように定義します。

  • $X_i > X_j$である$(i,j)$の個数$(1 \le i < j \le M)$

整数$N$が与えられます。
$N$行$N$列の行列$S$を考えます。上から$i$行目、左から$j$列目の要素を$S_{i,j}$とします。
ここで、$0 \le S_{i,j} \le 10^6$とします。
整数列$A$を次のように定義します。
  • $A_i = f([S_{i,1},S_{i,2}, \dots ,S_{i,N}])(1 \le i \le N)$
整数列$B$を次のように定義します。
  • $B_j = f([S_{1,j},S_{2,j}, \dots ,S_{N,j}])(1 \le j \le N)$
整数$K$が与えられます。
$f(A)+f(B)=K$である$S$を構築してください。構築不可能である時はそのことを報告してください。
答えが複数ある場合はその一例を求めてください。

制約

  • $1 \le N \le 1000$
  • $0 \le K \le 10^9$
  • $N,K$は整数

入力

$N\ K$

入力は$1$行で与えられます。
$N,K$が空白区切りで入力されます。

出力

構築不可能である場合はNoを1行に出力してください。
そうではない場合、Yesを1行に出力したあとに$N$行出力してください。
$i+1$行目には$S_{i,1},S_{i,2}, \dots ,S_{i,N}$を空白区切りで出力してください。

サンプル

サンプル1
入力
3 3
出力
Yes
3 2 3
2 3 1
1 3 2

$A_1 = f([3,2,3]) = 1$
$A_2 = f([2,3,1]) = 2$
$A_3 = f([1,3,2]) = 1$
$B_1 = f([3,2,1]) = 3$
$B_2 = f([2,3,3]) = 0$
$B_3 = f([3,1,2]) = 2$
よって、$A=[1,2,1]$,$B=[3,0,2]$となります。
$f(A)+f(B)=f([1,2,1])+f([3,0,2])=1+2=3$となり、この$S$は条件を満たします。

サンプル2
入力
5 0
出力
Yes
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

きれ~

サンプル3
入力
4 0
出力
Yes
7 6 5 4
6 5 4 3
5 4 3 2
4 3 2 1

はい。

サンプル4
入力
4 12
出力
Yes
4 3 2 1
3 4 1 2
2 1 4 3
1 2 3 4

この形、個人的に好きです。

サンプル5
入力
5 13
出力
Yes
9 8 3 8 2
4 6 8 3 9
7 5 4 1 5
6 2 6 2 4
6 1 6 5 9

これはヒントですが、このサンプルはほぼ意味ありません。

サンプル6
入力
1 1000000000
出力
No

このサンプルは意味ありますか?私はないと思います。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。