poj 2031 Rating

Rating

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
9
7 1 4
5
15 8
31 18
17

8
3
5
1 10
6
9
19
4 20
21

Sample Output

3
1 10
5 9
19
4 20
8 15
18 31
17 21

评分

描述

在圣彼得堡举行的两场地区比赛的参与者之一决定确定至少参加过一场比赛的所有团队的总体评分。
该参与者为每个团队分配了一个唯一的团队标识符，该标识符是从 1 到 100 的整数。对于每个竞赛团队，参赛团队的标识符根据他们在该竞赛中的位置写在一个列中。具有相同结果的团队的标识符写在同一行上。参与者从该比赛中最好的团队开始（将它们写在第一行），然后按照结果递减的顺序继续。
定义：如果恰好 K-1 支球队在那场比赛中表现更好，那么假设该球队在比赛中排名 K。
考虑以下两个竞赛结果的示例：
比赛编号 1

参加两场比赛的球队的总体评分定义如下：
1) 如果某支球队在两场比赛中的表现都比其他球队好（或在一场比赛中表现更好，而在另一场比赛中的成绩相同），那么前队的综合评分高于后队。
2) 如果有问题的一支球队在一场比赛中表现更好，而另一支球队在另一场比赛中表现更好，那么他们的总体评分取决于他们在两场比赛中的位置差异。因此，在我们的示例中，第 1 队在第一场比赛中优于第 5 队，相差 3 个位置，而在第二场比赛中更差，仅相差 1 个位置，因此第 1 队的整体评分高于第 5 队的评分。如果两场比赛的名次差异相同，则这支球队的总体评分相同。后者也适用于在两场比赛中表现相同的球队。
在我们的示例中，只有团队 1、4、5 和 9 参加了两次。第 1 队评分最高，评分相同的第 5 队和第 9 队次之，第 4 队评分最低。
对于参加过一场比赛的球队，不能总是确定他们在结果列表中的总体评分和位置。如果发生以下情况之一，他们将被列入总名单（其中两次参赛的球队已经根据上述规则获得了排名）：
A) 如果有一支球队参加了两场比赛并在其中一场比赛中分享了位置与该球队进行比赛，则后者的球队也与该球队共享总评分（如果此类球队不止一个，则他们的总评分应相同，否则无法确定该球队的总评分） ）。
B) 如果在总列表中有一个位置（在列表的开头、列表的末尾或某些行之间），则在此位置之前，只有在同一场比赛中表现更好的球队作为问题球队，在这个位置之后，只有在同一场比赛中表现更差的球队，那么这个球队在总名单中占据这个位置。如果不止一个团队声称在总名单中拥有相同的位置，那么他们的相互顺序由他们在比赛中的位置定义（查看下面的示例了解详细信息）。

?Team 3 将占据总榜首位（规则 B）。
?6、7队的位置无法确定。
? 团队 10 将与团队 1 共享总体评分（规则 A）。
?第 20 队将与第 4 队分享总体评分（规则 A）。
?第19队将占据第9队、第5队和第4队之间的位置（规则B）。
?第 8、15、17、18、21 和 31 队将完成总名单（规则 B）。但他们中的第一个将是第 15 和 8 队（排名第 6），其次是第 31 和 18 队（排名第 8）以及第 17 和 21 队（排名第 10）。
您的任务是编写一个程序，该程序将使用两场比赛的结果表和给定的规则创建总体评分列表。

输入

输入文件包含两个竞赛的描述，用空行分隔。每个描述都以包含单个整数 N (1 <= N <= 100) 的行开始，表示比赛结果表的行数。比赛结果表的每一行由一个或多个以空格分隔的团队标识符组成。
每个团队标识符在每场比赛的描述中最多出现一次。

输出

将一行或多行包含代表总体评分列表的团队标识符（以空格分隔）写入输出文件。具有相同评级（因此写在同一行）的团队按升序排列。未确定总体评分的团队不应出现在输出文件中。

样本输入

6 
9 
7 1 4 
5 
15 8 
31 18 
17 

8 
3 
5 
1 10 
6 
9 
19 
4 20 
21

样本输出

3 
1 10 
5 9 
19 
4 20 
8 15 
18 31 
17 21

代码：

#include 
#include 
#include 
#include 
#include 
using namespace std;
 
#define N 100
 
typedef struct team {
	int place[2];
	int number;
	int sum;
	int type;
	int location;
	int offset;
} Team;
 
Team tm[N + 1];
char line[300];
vector vds;
vector vsingle;
 
bool cmp(const Team* const a, const Team* const b) {
	if (a->sum != b->sum)
		return a->sum < b->sum;
	else
		return a->number < b->number;
}
 
bool cmpTeam(const Team* const a, const Team* const b) {
	if (a->location != b->location)
		return a->location < b->location;
	else if (a->offset != b->offset)
		return a->offset < b->offset;
	else
		return a->number < b->number;
}
 
class Check {
private:
	int min;
	int max;
public:
	Check() {
		min = 0;
		max = 101;
	}
	void setMax(int m) {
		if (m < max)
			max = m;
	}
	void setMin(int m) {
		if (m > min)
			min = m;
	}
 
	int result() {
		if (min < max) {
			return min;
		} else {
			return -1;
		}
	}
};
 
int main() {
	int t;
	char *ptr;
	scanf("%d", &t);
	getchar();
 
	int place = 1;
	for (int i = 1; i <= t; i++) {
		gets(line);
		ptr = strtok(line, " \0");    // 读入时可以处理多余的空格
		int count = 0;
		while (ptr != NULL) {
			count++;
			int number = atoi(ptr);
			tm[number].number = number;
			tm[number].type = 1;
			tm[number].place[0] = place;
			tm[number].sum = place;
			ptr = strtok(NULL, " ");
		}
		place += count;
	}
 
	scanf("%d", &t);
	getchar();
 
	place = 1;
	for (int i = 1; i <= t; i++) {
		gets(line);
		ptr = strtok(line, " \n");    // 读入时可以处理多余的空格
		int count = 0;
		while (ptr != NULL) {
			count++;
			int number = atoi(ptr);
			tm[number].number = number;
			tm[number].type += 2;
			tm[number].place[1] = place;
			tm[number].sum += place;
 
			if (tm[number].type == 3) {
				vds.push_back(&tm[number]);
			}
			ptr = strtok(NULL, " ");
		}
		place += count;
	}
	sort(vds.begin(), vds.end(), cmp);
	int last = 0;
	int index = 1;
	int count = 0;
	for (vector::iterator it = vds.begin(); it != vds.end(); ++it) {
		Team* tm = *it;
		if (tm->sum == last) {
			count++;
			tm->location = index;
		} else {
			index += count;
			count = 1;
			tm->location = index;
			last = tm->sum;
		}
	}
 
	for (int i = 1; i <= N; i++) {
		if (tm[i].type == 1 || tm[i].type == 2) {
			Check ck;
			bool eq = false;
			bool same = true;
			for (vector::iterator it = vds.begin(); it != vds.end();
					++it) {
				Team* td = *it;
				int ch = tm[i].sum - td->place[tm[i].type - 1];
				if (ch == 0) {
					if (!eq) {
						eq = true;
						tm[i].location = td->location;
					}else{
						if (tm[i].location!= td->location){
							same = false;
							break;
						}
					}
				} else if (ch < 0) {
					ck.setMax(td->location);
				} else {
					ck.setMin(td->location);
				}
			}
			if (!eq) {
				int re = ck.result();
				if (re > -1) {
					tm[i].location = re;
					tm[i].offset = tm[i].sum;
					vsingle.push_back(&tm[i]);
				}
			} else {
				if (same) {
					vsingle.push_back(&tm[i]);
				}
			}
		}
	}
	vds.insert(vds.end(), vsingle.begin(), vsingle.end());
	sort(vds.begin(), vds.end(), cmpTeam);
 
	int last_location = 0;
	int last_offset = 0;
	index = 1;
	count = 0;
	for (vector::iterator it = vds.begin(); it != vds.end(); ++it) {
		Team* tm = *it;
		if (tm->location == last_location && tm->offset == last_offset) {
			count++;
			tm->sum = index;
		} else {
			index += count;
			count = 1;
			tm->sum = index;
			last_location = tm->location;
			last_offset = tm->offset;
		}
	}
 
	last = vds[0]->sum;
	printf("%d", vds[0]->number);
	for (int i = 1; i < vds.size(); i++) {
		if (vds[i]->sum == last) {
			printf(" %d", vds[i]->number);
		} else {
			printf("\n%d", vds[i]->number);
			last = vds[i]->sum;
		}
	}
	puts("");
	return 0;
}