Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1588
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1588
Help the Federation
By Bruno Adami, Universidade de São Paulo - São Carlos 
Brazil
Timelimit: 1
The football federation hired you to organize the scoreboard of the tournament. You will receive a list with some past matches and you must sort the teams accordingly. A win grants 3 points, a draw 1 point and if the team lost it receives nothing.
Read carefully the regulation on how the scoreboard should be organized: First comes the team with more points. Then if there is a draw, the team with more wins should come first. If there is still a draw, the team with more goals should come first. At last, if none of the above sorting criterias is fulfilled, the team that comes first in the input should appear first.
Given the teams and the games, sort them and output the scoreboard.
Input
In the first line, there is an integer T (T ≤ 100), that indicates the number of test cases.
In the first line of each test case we have two numbers, N (2 ≤ N ≤ 20* or 2 ≤ N ≤ 100**) and M (1 ≤ M ≤ 100* or 1 ≤ M ≤ 1000**), indicating how many teams are in the championship and how many matches were already played. The next N lines contain the team names. They are all unique and contain only lowercase letters of the English alphabet. The following M lines contain the match information with the following format: X teamA Y teamB, indicating that the teamA played against the teamB and the first scored X goals and the second Y goals.The strings have size between 1 and 20 and the number of goals of a team during a match will be between 0 and 100. A team never plays with itself, but it can play any number of times with another team.
*for around 90% of the test cases;
**for the other cases.
Output
Output the sorted scoreboard team names, one per line. It is not necessary to print anything between the test cases!
| Sample Input | Sample Output |
|
3 2 2 palmeiras santos 1 palmeiras 2 santos 2 palmeiras 0 santos 2 2 b a 1 a 1 b 1 b 1 a 4 7 b a c d 2 a 1 b 1 b 1 a 2 c 3 a 4 b 2 d 0 b 1 c 1 b 0 c 7 d 1 b |
palmeiras santos b a b a d c |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define mp make_pair
#define pb push_back
#define MAXV 200100
using namespace std;
typedef vector<int> vi;
typedef pair < int, int> ii;
typedef pair<int, ii> iii;
typedef pair < iii, int> i4;
typedef long long int64;
struct node {
int pontos, vitorias, gols, pos;
node(int pontos = 0, int vitorias = 0, int gols = 0, int pos = 0)
: pontos(pontos)
, vitorias(vitorias)
, gols(gols)
, pos(pos)
{
}
};
int main()
{
ios::sync_with_stdio(false);
int n, a, b, p;
cin >> n;
string num;
while (n--) {
cin >> a >> b;
string s;
map < string, node> times;
map<int, string> resp;
for (int i = 0; i < a; i++) {
cin >> s;
times[s] = node(0, 0, 0, i);
resp[i] = s;
}
string t1, t2;
int p1, p2;
for (int i = 0; i < b; i++) {
cin >> p1 >> t1;
times[t1].gols += p1;
cin >> p2 >> t2;
times[t2].gols += p2;
if (p1 > p2) {
times[t1].pontos += 3;
times[t1].vitorias++;
} else if (p2 > p1) {
times[t2].pontos += 3;
times[t2].vitorias++;
} else {
times[t1].pontos++;
times[t2].pontos++;
}
}
map < string, node>::iterator it;
priority_queue pq;
for (it = times.begin(); it != times.end(); it++) {
pq.push(mp(mp(it->second.pontos, mp(it->second.vitorias, it->second.gols)), -it->second.pos));
}
while (!pq.empty()) {
cout << resp[-pq.top().second] << "\n";
pq.pop();
}
}
return 0;
}
Input
2 2
palmeiras
santos
1 palmeiras 2 santos
2 palmeiras 0 santos
2 2
b
a
1 a 1 b
1 b 1 a
4 7
b
a
c
d
2 a 1 b
1 b 1 a 2 c 3 a
4 b 2 d
0 b 1 c
1 b 0 c
7 d 1 b
Output
santos
b
a
b
a
d
c