QOJ.ac

QOJ

実行時間制限: 2.0 s メモリ制限: 256 MB 満点: 100 ハック可能 ✓

#11536. 计分板截图

統計

MITIT 2025 Winter Contest 顺利结束,共有 $K$ 支队伍参赛,Busy Beaver 需要为比赛撰写一份报告。

为了撰写报告,Busy Beaver 在比赛期间截取了 $N$ 张记分板的截图。每张截图都包含了拍摄时所有 $K$ 支队伍的分数。

遗憾的是,Busy Beaver 忘记了拍摄这些截图的顺序!他假设如果比赛期间没有进行分数修正,那么每支队伍的分数随时间推移应该是非递减的。基于这一假设,Busy Beaver 想要恢复截图的顺序。

请确定是否存在一种合法的顺序,使得没有任何队伍的分数随时间推移而减少。如果存在,请输出任意一种合法的顺序。

输入格式

第一行包含两个整数 $N$ 和 $K$ ($2 \leq N \leq 400$; $1 \leq K \leq 400$),分别表示截图的数量和队伍的数量。

接下来的 $N$ 行中,第 $i$ 行包含 $K$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ ($0 \leq a_{i,j} \leq 900$),其中 $a_{i, j}$ 表示第 $i$ 张截图中第 $j$ 支队伍的分数。

输出格式

如果存在合法的顺序,第一行输出 YES。第二行输出 $N$ 个整数 $b_1, \dots, b_N$,其中 $b_i$ 表示合法顺序中第 $i$ 张截图的原始索引。如果存在多种解,输出任意一种即可。

如果不存在合法的顺序,输出 NO

子任务

本题共有两个子任务:

  • ($20$ 分) $K = 1$。
  • ($80$ 分) 无额外限制。

样例

样例输入 1

3 2
1 1
0 0
0 1

样例输出 1

YES
2 3 1

说明 1

在第一个测试样例中,一种合法的截图顺序为:

  • 第二张截图:第 $1$ 支队伍分数为 $0$,第 $2$ 支队伍分数为 $0$。
  • 第三张截图:第 $1$ 支队伍分数为 $0$,第 $2$ 支队伍分数为 $1$。
  • 第一张截图:第 $1$ 支队伍分数为 $1$,第 $2$ 支队伍分数为 $1$。

样例输入 2

3 3
0 0 1
1 0 0
0 1 0

样例输出 2

NO

说明 2

在第二个测试样例中,不存在合法的顺序,因为无法排列这些截图使得每支队伍的分数随时间推移均非递减。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.