U192222 匹配
题目描述
有 $n$ 位毕业生（编号为 $1...n$）正在找工作，同时有 $n$ 家公司（编号为 $1...n$）正在招聘。
每位毕业生心中有一个公司排名，排名越靠前代表他对这个公司越感兴趣；这个排名由二维数组 $f$ 给出，$f[i][j]$ 代表在毕业生 $i$ 心中排名第 $j$ 位的公司编号。
例如 $n=3$：
```cpp
f = [2,3,1
1,2,3
2,1,3]
```
则对于 $1$ 号毕业生来说，公司排名为 $f[1] = [2,3,1]$，代表 $2$ 号公司最佳，$3$ 号公司次之，$1$ 号公司最差；对于 $2$ 号毕业生来说，公司排名为 $f[2] = [1,2,3]$；对于 $3$ 号毕业生来说，公司排名为 $f[3] = [2,1,3]$。
同时，每个公司有一个毕业生排名，排名越靠前代表公司认为这个毕业生越优秀。这个排名的由二维数组 $g$ 给出。
最终的目的是让公司和毕业生一一配对（一位毕业生选择恰好一个公司），设当前和 $i$ 号公司配对的毕业生为 $h[i]$，初始 $h[i]$ 都为 0（所有公司全部未配对）。
现在所有毕业生和公司达成协议，他们将重复以下流程，直到配对完成（所有 $h[i] \ne 0$ ）：
1. 遍历所有毕业生，若 $i$ 号毕业生还没有和任何公司配对，则他会向仍未拒绝过他的公司中最优秀（ $f[i]$ 中最靠前的）的公司发出工作申请。
2. 遍历所有公司，若 $i$ 号公司本轮中收到申请，则选出其中最优秀的一个人选（$g[i]$ 中最靠前的），设其为 $x$。首先公司向除了 $x$ 之外的本轮申请者发出拒绝，然后进行判断：
- 若 $h[i]=0$，则令 $h[i]=x$，即 $i$ 号公司和 $x$ 号毕业生配对；
- 若 $h[i]\ne 0$，且 $h[i]$ 的排名比 $x$ 靠后，则公司取消之前的配对，转而和 $x$ 配对：$h[i]=x$，同时 $i$ 公司向毕业生 $h[i]$ 发出拒绝；
- 若 $h[i]\ne 0$，且 $h[i]$ 的排名比 $x$ 靠前，则 $i$ 公司向毕业生 $x$ 发出拒绝；
3. 此时若所有 $h[i] \ne 0$ ，则结束；否则回到步骤1。
给定 $f,g$ 两个二维数组，请你编程实现上述过程，输出最终的配对方案 $h[1...n]$。
输入格式
输入一行2个整数，代表 $n$ 和随机种子 $seed$
为了避免输入量过大超时，本题采用以下方式进行输入（你可以复制下面代码作为输入部分）
```cpp
int n,seed;
cin>>n>>seed;
srand(seed);
for(int i=1;i
输出格式
输出一行 $n$ 个整数，代表 $h[1...n]$
说明/提示
样例1中 $n=3$：
```cpp
f = [2,1,3,
1,2,3,
2,1,3]
g = [3,1,2,
2,3,1,
1,2,3]
```
第一轮开始时，$h=[0,0,0]$:
- $1$ 号毕业生向 $2$ 号公司发出申请
- $2$ 号毕业生向 $1$ 号公司发出申请
- $3$ 号毕业生向 $2$ 号公司发出申请
- $1$ 号公司和 $2$ 号毕业生达成配对
- $2$ 号公司和 $3$ 号毕业生达成配对，向 $1$ 号毕业生发出拒绝
第二轮开始时，$h=[2,3,0]$:
- $1$ 号毕业生向 $1$ 号公司发出申请
- $1$ 号公司进行比较，$g[1] = [3,1,2]$，$1$ 号比当前 $h[1] = 2$ 排名更靠前，$1$ 号公司和 $1$ 号毕业生达成配对，向 $2$ 号毕业生发出拒绝
第三轮开始时，$h=[1,3,0]$:
- $2$ 号毕业生向 $2$ 号公司发出申请
- $2$ 号公司进行比较，$g[2] = [2,3,1]$，$2$ 号比当前 $h[2] = 3$ 排名更靠前，$2$ 号公司和 $2$ 号毕业生达成配对，向 $3$ 号毕业生发出拒绝
第四轮开始时，$h=[1,2,0]$:
- $3$ 号毕业生向 $1$ 号公司发出申请
- $1$ 号公司进行比较，$g[2] = [3,1,2]$，$3$ 号比当前 $h[1] = 1$ 排名更靠前，$1$ 号公司和 $3$ 号毕业生达成配对，向 $1$ 号毕业生发出拒绝
第五轮开始时，$h=[3,2,0]$:
- $1$ 号毕业生向 $3$ 号公司发出申请
- $3$ 号公司和 $1$ 号毕业生达成配对
第五轮结束后$h=[3,2,1]$，完成一一配对。
【数据范围】
对于所有测试点，$1\le n\le 5000, 0\le seed\le 10^9$，输入方式保证了 $f,g$ 数组中的每行都是 $1,2,...,n$ 的排列
子任务1（20分）：$1\le n\le 10$
子任务2（20分）：$1\le n\le 50$
子任务3（20分）：$1\le n\le 500$
子任务4（20分）：$1\le n\le 1000$
子任务5（20分）：$1\le n\le 5000$