|
Интернет-олимпиады
(Время: 1 сек. Память: 16 Мб Сложность: 33%)
Многим известно о проекте «Интернет-олимпиады по информатике», расположенном в сети Интернет по адресу http://neerc.ifmo.ru/school/io/, где проводятся онлайн-олимпиады для школьников в двух номинациях: базовой и усложненной. Ваша задача состоит в том, чтобы написать программу, обрабатывающую результаты Интернет-олимпиады, то есть определяющую: какие команды в какой номинации будут участвовать в следующей олимпиаде.
Правила перехода команд из одной номинации в другую таковы. Задачи усложненной номинации решают следующие команды:
- участвовавшие в предыдущей олимпиаде в усложненной номинации и решившие хотя бы одну задачу;
- участвовавшие в предыдущей олимпиаде в базовой номинации, решившие хотя бы одну задачу, и при этом решившие либо столько же задач, сколько команда-победитель, либо строго больше задач, чем команда, занявшая медианное место среди команд, решивших хотя бы одну задачу (место с номером k/2, где k - число команд, участвовавших в базовой номинации, решивших хотя бы одну задачу, округление производится вниз).
Все остальные команды участвуют в следующей олимпиаде в базовой номинации. В этой задаче мы считаем, что никакие новые команды не регистрируются для участия в следующей олимпиаде.
Напомним также, что при подведении итогов одной олимпиады команды сортируются по убывании количества решенных задач, а при равенстве количества решенных задач - по возрастанию штрафного времени.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа: n и m - соответственно, количество команд, участвовавших в базовой и усложненной номинациях (1 ≤ n, m ≤ 1000).
После этого идут n строк, описывающих результаты команд, участвовавших в базовой номинации. Каждая из этих строк содержит три целых числа, разделенных пробелами, - id, s, t - соответственно, уникальный идентификатор команды, количество решенных задач и штрафное время. Количество решенных задач - целое число от 0 до 12, а штрафное время - целое число от 0 до 20000. Идентификатор команды - это целое число от 1 до 2000.
После этого идут m строк, описывающих результаты усложненной номинации в таком же формате.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите число k команд, которые допускаются до участия в усложненной номинации в следующей олимпиаде. Вторая строка должна содержать k целых чисел - идентификаторы этих команд в возрастающем порядке.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 6 3
1 1 45
2 4 678
3 5 1000
4 5 894
5 2 343
6 3 555
1998 0 0
1999 1 34
2000 3 366 | 4
3 4 1999 2000 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
