Redistributing Gifts

题目描述

农夫 John 有 $N$ 份礼物，编号为 $1\ldots N$，准备送给他的 $N$ 头奶牛，奶牛也编号为 $1\ldots N$（$1\le N\le 500$）。每头奶牛都有一个愿望清单，它是所有 $N$ 份礼物的一个排列；奶牛更喜欢清单中靠前出现的礼物，而不是靠后出现的礼物。 FJ 很懒，就把礼物 $i$ 分配给奶牛 $i$（对所有 $i$ 都如此）。现在，奶牛们聚在一起，决定重新分配礼物，使得重新分配后，每头奶牛最终得到的要么是她原来得到的同一份礼物，要么是她相比原先分配到的礼物更喜欢的礼物。 对于每个 $i$（从 $1$ 到 $N$），计算奶牛 $i$ 在重新分配后最多能希望得到的、她最喜欢的礼物。

输入格式

第一行包含 $N$。接下来的 $N$ 行每行包含一头奶牛的偏好列表。保证每一行都是 $1\dots N$ 的一个排列。

输出格式

请输出 $N$ 行，第 $i$ 行输出奶牛 $i$ 在重新分配后最多能希望得到的最喜欢的礼物。

4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4

1
3
2
4

提示

在这个例子中，有两种可能的重新分配： 原始分配：奶牛 $1$ 得到礼物 $1$，奶牛 $2$ 得到礼物 $2$，奶牛 $3$ 得到礼物 $3$，奶牛 $4$ 得到礼物 $4$。 奶牛 $1$ 得到礼物 $1$，奶牛 $2$ 得到礼物 $3$，奶牛 $3$ 得到礼物 $2$，奶牛 $4$ 得到礼物 $4$。 注意，奶牛 $1$ 和 $4$ 都无法希望得到比原先分配更好的礼物。然而，奶牛 $2$ 和 $3$ 都可以。 评分： 测试点 2-3 满足 $N\le 8$。 测试点 4-11 没有额外限制。 题目来源：Benjamin Qi

标签: USACO|2022|Silver

来源

USACO|2022|Silver