問題一覧 > 通常問題

No.2263 Perms

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 59
作問者 : milkcoffee / テスター : とりゐ sotanishy
お気に入りにしたユーザー ProblemId : 9331 / 自分の提出
問題文最終更新日: 2023-04-07 00:12:58
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 383 (順位表) の他の問題:

Problem Statement

There are $M$ permutations $(P_1,P_2,\cdots,P_N)$ of $(1,2,\cdots,N)$. The number of permutations with $P_i = j$ was $A_{i,j}$.

Does there exist a tuple of $M$ permutations satisfying the condition?

If one exists, find such a tuple of permutations.

Input

$N$ $M$
$A_{1,1}$ $\cdots$ $A_{1,N}$
$\vdots$
$A_{N,1}$ $\cdots$ $A_{N,N}$

  • $2 \leq N,M \leq 50$
  • $0 \leq A_{i,j} \leq M$ $(1 \leq i,j \leq N)$
  • All inputs are integers.

Output

If no tuple of permutations satisfying the condition exists, print -1.
If one exists, print $M$ lines in total, with the $i$-th permutation on the $i$-th line.
If there are multiple answers, you may print any of them.

Sample

Sample 1
Input
3 2
0 1 1
0 1 1
2 0 0
Output
2 3 1
3 2 1

One possibility is that the $1$st permutation is $(2,3,1)$ and the $2$nd permutation is $(3,2,1)$.
The $2$ permutations may be printed in any order.

Sample 2
Input
2 5
2 3
2 3
Output
-1

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