上题目：

Description

One of the participants of both regional contests which took place in St. Petersburg decided to determine overall rating for all teams that took part in at least one contest.
This participant assigned each team a unique team identifier, which was an integer from 1 to 100 inclusively. For each contest team identifiers of the participating teams were written in a column according to their place in that contest. Identifiers of the teams that had equal results were written on the same line. The participant started with the team(s) that was(were) the best in that contest (writing them on the first line) and continued in the order of decreasing results.
Definition: Let’s say that the team has place K in the contest if exactly K-1 teams performed in that contest better.

Consider the following examples of two contests’ results:

The overall rating for the teams which took part in both contests is defined in the following way:

1) If some team performed better in both contests than some other team (or better in one contest and with the same result in the other contest) then the overall rating of the former team is higher than the rating of the latter team.

2) If one of the teams in question performed better in one contest and the other team performed better in another contest then their overall rating depends on the difference of their places in both contests. So, in our example team 1 is better than team 5 in the first contest with a difference of 3 places and worse in the second contest with a difference of only 1 place, therefore the overall rating of team 1 is higher than team 5’s one. If the difference of the places is the same for both contests then that teams have the equal overall ratings. The latter is also true for the teams that performed equally in both contests.

In our example only teams 1, 4, 5, and 9 participated twice. Team 1 has the highest rating, teams 5 and 9 with the equal rating follow, and team 4 has the lowest rating.

For the teams that participated in one contest only the overall rating and their position in the resulting list cannot be always determined. They are included in the overall list (where the teams which participated twice already placed according to the rules above) if one of the following takes place:

A) If there is a team that participated in both contests and shared the place in one of the contests with the team in question then the latter team shares the overall rating with this team too (if there is more than one such team, then they all should have the same overall rating, otherwise the overall rating of the team in question cannot be determined).

B) If there is a position in the overall list (either at the beginning of the list, at the end of the list, or between some lines), such that before this position only the teams are located which performed better in the same contest as the team in question and after this position only the teams are located which performed worse in the same contest as the team in question, then the team in question occupies this position in the overall list. If more than one team claim to have the same position in the overall list, then their mutual order is defined by their places in their contests (look at the example below for details).

?Team 3 will occupy the first place in the overall list (rule B).

?The positions of teams 6 and 7 cannot be determined.

?Team 10 will share the overall rating with team 1 (rule A).

?Team 20 will share the overall rating with team 4 (rule A).

?Team 19 will occupy the position between teams 9, 5 and team 4 (rule B).

?Teams 8, 15, 17, 18, 21, and 31 will finish the overall list (rule B). But the first of them will be teams 15 and 8 (that took 6th place) followed by teams 31 and 18 (that took 8th place) and teams 17 and 21 (that took 10th place).

Your task is to write a program that will create the overall rating list using the result tables of two contests and the given rules.

Input

The input file contains a description of the two contests, which are separated by an empty line. Each description starts with a line containing the single integer N (1 <= N <= 100) that indicates how many lines of the contest result table follow. Each line of the contest result table consists of one or more team identifiers separated by spaces.

Every team identifier occurs at most once in the description of each contest.

Output

Write to the output file one or more lines with the team identifiers (separated by spaces) that represent the overall rating list. The teams that share the same rating (thus written on the same line) is written in ascending order. The teams for which the overall rating is not determined should be absent in the output file.

Sample Input

6<br></br>9<br></br>7 1 4<br></br>5<br></br>15 8<br></br>31 18<br></br>17<br></br><br></br>8<br></br>3<br></br>5<br></br>1 10<br></br>6<br></br>9<br></br>19<br></br>4 20<br></br>21<br></br>

Sample Output

3<br></br>1 10<br></br>5 9<br></br>19<br></br>4 20<br></br>8 15<br></br>18 31<br></br>17 21

看到这题目通过率16％一下子就有点怕怕……看了题目感觉还行，就是很烦。想了一下，大概想出个思路，就是把参加了两次比赛的队伍的两次比赛名次分别加起来，然后排序，就能够得到前两条规则需要的排名，第三条规则也比较方便，只要遍历一次就OK了。第四条规则一开始没想清楚，主要是对于没有同时参加同一场比赛的队伍的排名理解没有搞清楚。这时候犯了个错误，急着写代码了。写出来代码很乱，有7层嵌套居然……看得都头晕……自然没有AC。WA了，受不了，直接找比赛当年的测试数据。20个数据对了17个，18，只有一点点错误，19，20就错的很离谱。仔细调试了一下数据18，发现算法有问题……悲剧中的悲剧……时间不早了，于是睡觉。睡觉前仔细地想了一下第四条规则，想出一个比较方便的办法。

前三条规则不变，数组多开1位，存放表示只参加了某场比赛的那场的名次，然后插入的时候直接把名次复制上面那位，到时候排序的时候进行双关键字排序。具体执行的时候又可以把第一个关键字乘以一个很大的数字，比如10000，然后加上第二个关键字，这样子只要一次排序。不过就是因为这个小技巧……又WA了一次。把无法确定位置的队伍排序进去了。

贴代码：

#include #include

const int n = 100;

int rate[110][5];
//rate[i][0]表示第一次比赛排名,[i][1]表示第二次比赛排名,
//对于[i][2]，两次比赛都参加的就是前两次比赛相加，通过第3条规则确定排名的就是复制与他对应的队伍的排名
//通过第4条规则确定排名的就是复制他上面离他最近的那个队伍的数值。
//[i][3]对于参加了两次比赛以及通过第3条规则确定排名的队伍都是0，通过第四条规则确定排名的队伍就是参加
//的那次比赛的排名。这样子进行一次排序，[i][2]为主关键字，[i][3]为次关键字就能得到答案
int a[110][2];
char tmp[10000];

void aSort(int a[110][2])
{
int i, j, tmp;
for(i=1; i<=n; i++){
for(j=n; j>i; j–){
if(a[j][0] < a[j-1][0]){
tmp = a[j][0];
a[j][0] = a[j-1][0];
a[j-1][0] = tmp;
tmp = a[j][1];
a[j][1] = a[j-1][1];
a[j-1][1] = tmp;
}
}
}
}

int main()
{
int n1, n2, now, num, i, j, k, t, Changed, upMax, upMin, downMax, downMin;
memset(rate, 0, sizeof(rate));
for (t = 0; t < 2; t++) {
scanf(“%d\n”, &n1);
now = 1;
for (i = 1; i <= n1; i++) {
num = 0;
gets(tmp);
while(strlen(tmp) == 0)
gets(tmp);
for (j = 0; j < strlen(tmp); j++) {
if (tmp[j] <= ‘9’ && tmp[j] >= ‘0’) {
sscanf(tmp + j, “%d”, &k);
rate[k][t] = now;
num++;
while (tmp[j] <= ‘9’ && tmp[j] >= ‘0’) {
j++;
}
}
}
now += num;
}
}
for (i = 1; i <= n; i++) {
if (rate[i][0] != 0 && rate[i][1] != 0) {
rate[i][2] = (rate[i][0] + rate[i][1]);
}
if (rate[i][0] == 0 || rate[i][1] == 0){
rate[i][3] = rate[i][0] + rate[i][1];
}
}

Changed = true;
Changed = false;
for (t = 0; t <= 1; t++) {
for (i = 1; i <= n; i++) {
if (rate[i][2] == 0 && rate[i][t] != 0) {
//通过规则A确定排名
for (j = 1; j <= n; j++){
if (rate[j][2] != 0 && rate[j][3] == 0 && rate[j][t] == rate[i][t]) {
if(rate[i][2] == 0 || rate[i][2] == rate[j][2])
rate[i][2] = rate[j][2];
else{
rate[i][2] = 0;
Changed = 3;//多种不同位置冲突，
&nbs; p; break;
}
}
}
if(rate[i][2] != 0){
Changed = true;
rate[i][3] = 0;
continue;
}
if(Changed == 3){//多种不同位置冲突
Changed = false;
continue;
}
//通过规则B确定排名
upMax = downMax = -100000000;
upMin = downMin = 100000000;
for (j=1; j<=n; j++){
if (rate[j][2] != 0 && rate[j][3] == 0){
if(rate[j][t] != 0 && rate[j][t] < rate[i][t]){
if(upMax < rate[j][2])
upMax = rate[j][2];
if(upMin > rate[j][2])
upMin = rate[j][2];
}
if(rate[j][t] != 0 && rate[j][t] > rate[i][t]){
if(downMax < rate[j][2])
downMax = rate[j][2];
if(downMin > rate[j][2])
downMin = rate[j][2];
}
}
}
if(upMax >= downMin)
continue;
if(upMax == -100000000 && upMin == 100000000 && downMin != 100000000){
Changed = true;
rate[i][2] = downMin - 1;
continue;
}
if(downMax == -100000000 && downMin == 100000000 && upMax != -100000000){
Changed = true;
rate[i][2] = upMax + 1;
continue;
}
rate[i][2] = upMax;
Changed = true;
continue;
}
}
}

memset(a, 0, sizeof(a));
for(i=1; i<=n; i++) {
if (rate[i][2] != 0) {
a[i][0] = rate[i][2]*10000 + rate[i][3];
a[i][1] = i;
}
}
aSort(a);
for(i=1; i<=n; i++){
if(a[i][0] == 0)
continue;
memset(tmp, 0, sizeof(tmp));
for(j=1; j<=n; j++){
if(a[j][0] == a[i][0])
sprintf(tmp + strlen(tmp), “%d “, a[j][1]);
}
tmp[strlen(tmp)-1] = ‘\0’;
printf(“%s\n”, tmp);
while(a[i][0] == a[i+1][0] && i <= n)

; i++;
}
/for(i=1; i<=n; i++){
if(a[i][0] == 0)
continue;
printf(“%d %d %d %d\n”, a[i][1], a[i][0], rate[a[i][1]][2], rate[a[i][1]][3]);
}/
}