Codeforces Round 595 (Div. 3) |
---|
Закончено |
Единственное ограничение между простой и сложной версиями — ограничения.
Вам задано $$$n$$$ отрезков на координатной оси $$$OX$$$. Отрезки могут пересекаться, вкладываться или даже совпадать. $$$i$$$-й отрезок равен $$$[l_i; r_i]$$$ ($$$l_i \le r_i$$$) и покрывает все такие целочисленные точки $$$j$$$, что $$$l_i \le j \le r_i$$$.
Целочисленная точка называется плохой, если она покрыта строго больше, чем $$$k$$$ отрезками.
Ваша задача — удалить минимальное количество отрезков таким образом, чтобы плохих точек не осталось вообще.
Первая строка входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 200$$$) — количество отрезков и максимальное количество отрезков, которым может быть покрыта каждая целочисленная точка.
Следующие $$$n$$$ строк содержат отрезки. $$$i$$$-я строка содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le 200$$$) — границы $$$i$$$-го отрезка.
В первой строке выведите одно целое число $$$m$$$ ($$$0 \le m \le n$$$) — минимальное количество отрезков, которое надо удалить, чтобы не осталось плохих точек.
Во второй строке выведите $$$m$$$ различных целых чисел $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i \le n$$$) — индексы отрезков, которые вы удаляете, в любом порядке. Если существует несколько возможных ответов, вы можете вывести любой из них.
7 2 11 11 9 11 7 8 8 9 7 8 9 11 7 9
3 1 4 7
5 1 29 30 30 30 29 29 28 30 30 30
3 1 2 4
6 1 2 3 3 3 2 3 2 2 2 3 2 3
4 1 3 5 6
Название |
---|