4416. Тестирующая система

Юный программист Саша написал свою первую тестирующую систему. Он был так рад тому, что она успешно скомпилировалась, что решил пригласить школьных друзей на свой собственный контест.

Однако в конце тура выяснилось, что система не умеет сортировать команды в таблице результатов. Помогите Саше реализовать эту сортировку.

Команды упорядочиваются по правилам ICPC:

· по количеству решённых задач в порядке убывания;

· при равенстве количества решённых задач – по штрафному времени в порядке возрастания;

· при прочих равных – по номеру команды в порядке возрастания.

Вход. Первая строка содержит количество команд n (1 ≤ n ≤ 10⁵), участвующих в контесте. В i-ой из следующих n строк записано количество решённых задач s (0 ≤ s ≤ 100) и штрафное время t (0 ≤ t ≤ 10⁵) команды с номером i.

Выход. Выведите n чисел – номера команд в отсортированном порядке.

Пример входа	Пример выхода
5 3 50 5 720 1 7 0 0 8 500	5 2 1 3 4

РЕШЕНИЕ

сортировка

Анализ алгоритма

Команду будем представлять в виде структуры, содержащей следующие поля:

· номер команды;

· штрафное время;

· количество решенных задач;

Для решения задачи необходимо реализовать компаратор – функцию сравнения двух команд в соответствии с правилами 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;

};

Объявим массив команд acm.

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;

}

Сортируем команды в соответствии с заданными условиями.

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;

}

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();

}

}

Python реализация

Читаем количество команд n.

n = int(input())

Строим список команд teams. Каждая команда представляет собой кортеж вида (количество решенных задач, сумма штрафных минут, номер команды).

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 = ' ')