Testing System#4416
Bejelentkezés

Testing System (Megoldási útmutató)

We'll represent a team as a structure containing the following fields:

To solve the problem, it is necessary to implement a comparator — a function that compares two teams according to the ICPC rules, and then perform the sorting.

Algorithm implementation

Declare a team structure — an ICPC competition participant, including the team number, penalty time, and number of solved problems.

struct person
{
  int id, penalty_time, problems;
} *acm;

Implement the function cmp — a comparator for sorting the competition participants.

int cmp(person a, person b)
{

Sort by the number of solved problems in descending order.

  if (a.problems != b.problems) return a.problems > b.problems;

If the number of solved problems is equal, sort by penalty time in ascending order.

  if (a.penalty_time != b.penalty_time) 
    return a.penalty_time < b.penalty_time;

If all previous criteria are equal, sort by team number in ascending order.

  return a.id < b.id;
}

The main part of the program. Allocate memory for the array of teams.

scanf("%d",&n);
acm = new person[n];

Read the data about the teams.

for (i = 0; i < n; i++)
{
  scanf("%d %d",&acm[i].problems,&acm[i].penalty_time);
  acm[i].id = i + 1;
}

Sort the teams according to the given conditions.

sort(acm,acm+n,cmp);

Print the team numbers in the order of their placement in the results table.

for (i = 0; i < n; i++)
  printf("%d",acm[i].id);
printf("\n");

delete[] acm;

Algorithm implementation — vector

Declare a team structure — an ICPC competition participant, including the team number, penalty time, and number of solved problems.

struct person
{
  int id, penalty_time, problems;
};

Declare an array of teams .

vector<person> acm;

Implement the function cmp — a comparator for sorting the competition participants.

int cmp(person a, person b)
{

Sort by the number of solved problems in descending order.

  if (a.problems != b.problems) return a.problems > b.problems;

If the number of solved problems is equal, sort by penalty time in ascending order.

  if (a.penalty_time != b.penalty_time) 
    return a.penalty_time < b.penalty_time;

If all previous criteria are equal, sort by team number in ascending order.

  return a.id < b.id;
}

The main part of the program. Read the input data.

scanf("%d",&n);
acm.resize(n);
for (i = 0; i < n; i++)
{
  scanf("%d %d",&acm[i].problems,&acm[i].penalty_time);
  acm[i].id = i + 1;
}
C++

Sort the teams according to the given conditions.

sort(acm.begin(),acm.end(),cmp);

Print the team numbers in the order of their placement in the results table.

for (i = 0; i < n; i++)
  printf("%d ",acm[i].id);
printf("\n");

Algorithm implementation — build-in comparator

#include <cstdio>
#include <algorithm>
using namespace std;

int n, i, ptr;
struct person
{
  int id, penalty_time, problems;
  int operator< (const person &a) const
  {
    if (problems != a.problems) return problems > a.problems;
    if (penalty_time != a.penalty_time)
      return penalty_time < a.penalty_time;
    return id < a.id;
  }
} *acm;

int main(void)
{
  scanf("%d",&n);
  acm = new person[n];

  for (i = 0; i < n; i++)
  {
    scanf("%d %d",&acm[i].problems,&acm[i].penalty_time);
    acm[i].id = i + 1;
  }

  sort(acm,acm+n);
  
  for (i = 0; i < n; i++)
    printf("%d ",acm[i].id);
  printf("\n");
  delete[] acm;
  return 0;
}
C++

Java implementation

import java.util.*;

class Person
{
  int problems;
  int penalty_time;  
  int id;
  
  public Person(int problems, int penalty_time, int id) 
  {
    this.problems = problems;
    this.penalty_time = penalty_time;    
    this.id = id;
  }
}

public class Main 
{
  public static class MyFun implements Comparator<Person>
  {
    public int compare(Person a, Person b)
    {
      if (a.problems == b.problems && a.penalty_time == b.penalty_time) return a.id - b.id;
      if (a.problems == b.problems) return a.penalty_time - b.penalty_time;
      return b.problems - a.problems;
    }
  }
	
  public static void main(String[] args) 
  {
    Scanner con  = new Scanner(System.in);
    int n = con.nextInt();
    Person[] p = new Person[n];

    for (int i = 0; i < n; i++)
      p[i] = new Person(con.nextInt(), con.nextInt(), i+1);

    Arrays.sort(p, new MyFun());
        
    for (int i = 0; i < n; i++)
      System.out.print(p[i].id + " ");
    
    con.close();
  }
}
Java

Python implementation

Read the number of teams .

n = int(input())

Build the list of teams . Each team is represented as a tuple in the format:

(number of problems solved, total penalty minutes, team number)

teams = []
for id in range(1, n + 1):
  problems, penalty_times = map(int, input().split())
  teams.append((problems, penalty_times, id))

Sort the teams according to the given conditions.

teams.sort(key = lambda team: (-team[0], team[1], team[2]))

Print the team numbers in the order they appear in the final ranking.

for t in teams:
  print(t[2], end = ' ')