問題一覧 > 通常問題

No.1087 Inversion Number of Inversion Numbers

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 15
作問者 : tyawanmusi / テスター : QCFium
お気に入りにしたユーザー ProblemId : 4220 / 自分の提出
問題文最終更新日: 2020-06-20 15:30:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 253 (順位表) の他の問題:

Problem Statement

For an integer sequence $X$ of length $M$, define $f(X)$ as follows.

  • The number of pairs $(i,j)$ such that $X_i > X_j$ $(1 \le i < j \le M)$

You are given an integer $N$.
Consider a matrix $S$ with $N$ rows and $N$ columns. Let $S_{i,j}$ denote the element in the $i$-th row from the top and the $j$-th column from the left.
Here, $0 \le S_{i,j} \le 10^6$.
Define the integer sequence $A$ as follows.
  • $A_i = f([S_{i,1},S_{i,2}, \dots ,S_{i,N}])(1 \le i \le N)$
Define the integer sequence $B$ as follows.
  • $B_j = f([S_{1,j},S_{2,j}, \dots ,S_{N,j}])(1 \le j \le N)$
You are given an integer $K$.
Construct $S$ such that $f(A)+f(B)=K$. If this is impossible, report so.
If there are multiple answers, find any one of them.

Constraints

  • $1 \le N \le 1000$
  • $0 \le K \le 10^9$
  • $N,K$ are integers

Input

$N\ K$

The input is given in $1$ line.
$N,K$ are given separated by a space.

Output

If the construction is impossible, print No on 1 line.
Otherwise, print Yes on 1 line, and then print $N$ lines.
On line $i+1$, print $S_{i,1},S_{i,2}, \dots ,S_{i,N}$ separated by spaces.

Sample

Sample 1
Input
3 3
Output
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$
Thus, $A=[1,2,1]$, $B=[3,0,2]$.
We get $f(A)+f(B)=f([1,2,1])+f([3,0,2])=1+2=3$, so this $S$ satisfies the condition.

Sample 2
Input
5 0
Output
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

So pretty~

Sample 3
Input
4 0
Output
Yes
7 6 5 4
6 5 4 3
5 4 3 2
4 3 2 1

Yep.

Sample 4
Input
4 12
Output
Yes
4 3 2 1
3 4 1 2
2 1 4 3
1 2 3 4

Personally, I like this shape.

Sample 5
Input
5 13
Output
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

As a hint: this sample is almost meaningless.

Sample 6
Input
1 1000000000
Output
No

Does this sample have any point? I don't think it does.

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