問題一覧 > 通常問題

No.1087 転倒数の転倒数

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

問題文

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

  • Xi>Xjである(i,j)の個数(1≤i<j≤M)

整数Nが与えられます。
N行N列の行列Sを考えます。上からi行目、左からj列目の要素をSi,jとします。
ここで、0≤Si,j≤106とします。
整数列Aを次のように定義します。
  • Ai=f([Si,1,Si,2,…,Si,N])(1≤i≤N)
整数列Bを次のように定義します。
  • Bj=f([S1,j,S2,j,…,SN,j])(1≤j≤N)
整数Kが与えられます。
f(A)+f(B)=KであるSを構築してください。構築不可能である時はそのことを報告してください。
答えが複数ある場合はその一例を求めてください。

制約

  • 1≤N≤1000
  • 0≤K≤109
  • N,Kは整数

入力

N K

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

出力

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

サンプル

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

A1=f([3,2,3])=1
A2=f([2,3,1])=2
A3=f([1,3,2])=1
B1=f([3,2,1])=3
B2=f([2,3,3])=0
B3=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もしくは右上の雲マークをクリックしてアカウントを作成してください。