Тестувальна система#4416
Увійти

Тестувальна система (Розбір)

Команду будем представляти у вигляді структури, що містить наступні поля:

Для вирішення задачі необхідно реалізувати компаратор — функцію порівняння двох команд відповідно до правил ICPC, а потім виконати сортування.

Реалізація алгоритму

Оголосимо структуру команди — учасника ICPC змагання, що включає номер команди, штрафний час і кількість вирішених задач.

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

Реалізуємо функцію cmp — компаратор для сортування учасників змагання.

int cmp(person a, person b)
{

Сортуємо за кількістю вирішених задач у порядку спадання.

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

При рівності кількості вирішених задач — сортуємо за штрафним часом у порядку зростання.

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

При інших рівних — сортуємо за номером команди у порядку зростання.

  return a.id < b.id;
}

Основна частина програми. Виділяємо пам'ять під масив команд.

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,cmp);

Виводимо номери команд у порядку їх розташування в таблиці результатів.

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

delete[] acm;

Реалізація алгоритму — вектор

Оголосимо структуру команди — учасника ICPC змагання, що включає номер команди, штрафний час і кількість вирішених задач.

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

Оголосимо масив команд .

vector<person> acm;

Реалізуємо функцію cmp — компаратор для сортування учасників змагання.

int cmp(person a, person b)
{

Сортуємо за кількістю вирішених задач у порядку спадання.

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

При рівності кількості вирішених задач — сортуємо за штрафним часом у порядку зростання.

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

При інших рівних — сортуємо за номером команди у порядку зростання.

  return a.id < b.id;
}

Основна частина програми. Читаємо вхідні дані.

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(acm.begin(),acm.end(),cmp);

Виводимо номери команд у порядку їх розташування в таблиці результатів.

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

Реалізація алгоритму — вбудований компаратор

#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 реалізація

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 реалізація

Читаємо кількість команд .

n = int(input())

Будуємо список команд . Кожна команда представляє собою кортеж виду

(кількість вирішених задач, сума штрафних хвилин, номер команди)

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

Сортуємо команди відповідно до заданих умов.

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

Виводимо номери команд у порядку їх розташування в таблиці результатів.

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