比赛场次 | 36 |
---|---|
比赛名称 | 2009暑期培训 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2009-07-09 08:30:03 |
结束时间 | 2009-07-09 11:30:03 |
开放分组 | 全部用户 |
注释介绍 | 2009暑假培训3 |
题目名称 | 速配游戏(无数据) |
---|---|
输入输出 | match.in/out |
时间限制 | 1000 ms (1 s) |
内存限制 | 128 MiB |
测试点数 | 10 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
maxiem | EEEEEEEEEE | 0.000 s | 0.00 MiB | 0 |
题目描述:
有一个速配电视节目。N位男士和N位女士要在摄像机前选出他们合适的伴侣。每位女士按照其对每位男士作为配偶的偏爱程度给每位男士排名次,每位男士也按照其对每位女士作为配偶的偏爱程度给每位女士排名次。这些名次不允许并列。然后每位男士将向心仪的对象求婚,经过“残酷”的竞争之后各自找到适合的伴侣。
最开始的时候每位男士都没有被任何一位女士拒绝。求婚环节会经过很多轮进行,每一轮:
(1)每位男士从还没有拒绝过自己的女士中选出自己认为最理想的一个,并向她求婚。
(2)每位女士在所有这一轮中从向她求婚的男士中选出自己认为最理想的一个,并不答应,也不拒绝。她把其余向她求婚的男士都婉言拒绝掉。
经过若干轮求婚之后,在某一轮,幸运的事情发生了:所有的女士都恰好有一个求婚者,所有的男士都找到一个心仪的对象。主持人将继续指出这个配对方式的神奇之处:没有任意的两个配对,例如男士A和女士a配对,男士B和女士b配对,使得在A心目中b较a更理想,而且在b心目中A较B更理想(这样A和b就会“私奔”)。因此,主持人总结说,这个配对是非常合理的。(他知道,这种情况是一定会发生的。)
主持人在节目之前已经知道男士和女士之间的偏爱情况,他想预先知道最后的匹配结果是怎么样的,你能帮帮他吗?
输入格式:
第1行包括一个数字N(1≤N≤1000)
以下N×2行,每行有N个数字。第i+1行(1≤i≤N)表示编号为i的男士对女士们的排序(从最喜欢的到最不喜欢的)。第N+j+l行(1≤j≤N)表示编号为j的女士对男士们的排序(同样从最喜欢的到最不喜欢的)。
输出格式:
N行,每行包括一个数字。第i行的数字表示与编号为i的男士匹配的女士的编号。
输入输出样例
match.in
3
1 2 3
2 3 1
2 1 3
3 2 1
2 3 1
2 3 1
match.out
3
2
1