C. Согласование
Задачу добавил: alef
Успешно сдано решений: 7
Министр промышленности Силантий, понятное дело, не преминул поинтересоваться: чему население обучать планируется? Министр науки Фалалей чуть замешкался, но нашёл аргумент. Вот, к примеру, уже год как в царстве разработали почтовый сервис. Вот только население не пользуется им, всё заморские сервисы предпочитает. А почему — да просто не умеет! Ежели обучить, сразу все пользоваться начнут. И министр финансов Дормидонт тут же поддержал: можно ещё обучить население, как оплату разных услуг онлайн осуществлять. А чтобы активнее учились, разрешать такую оплату только тем, у кого сертификат будет. Да и другие министры подтянулись, сказали, что у них много предложений, только подготовить документы надо.
Поясним, как работает канцелярия царя Пантелеймона. С 8:00 до 10:00 — время, когда объявляются вердикты по документам: какие подписаны, какие отклонены. C 12:00 до 15:00 — время, когда документы можно отдать на рассмотрение. C 16:00 до 18:00 — время, когда принимаются решения по документам: будут ли они отклонены или переданы на подпись царю.
Канцелярия может рассматривать документ по каждому предложению не более $$$d$$$ дней, после чего должна либо передать документ на подпись царю, либо отклонить. Если документ отклоняется, его авторы тут же вносят правки, и документ вновь поступает в канцелярию. После этого у канцелярии вновь есть $$$d$$$ дней на его рассмотрение (при $$$d=1$$$ вердикт по документу, принятому на рассмотрение сегодня, должен быть объявлен завтра, и т.д.).
Всего министры сделали $$$n$$$ предложений. Документ по предложению $$$\#j$$$ поступает в канцелярию в день $$$t_j$$$. Начальник канцелярии Дорофей знает, что царь Пантелеймон предпочитает подписывать сразу несколько документов: не менее $$$k$$$ штук за один раз. Чтобы каждый раз приносить царю на подпись $$$k$$$ или больше документов, Дорофей может отклонять какие-либо документы, тем самым задерживая их подписание.
Конечно, каждый документ может быть отклонён неоднократно, но каждый факт отклонения документа очень огорчает министра, который его вносил. Дорофей хочет, чтобы максимальное количество раз, которое он отклонит один и тот же документ, было минимально возможным. Ваша задача — определить это количество, а также сформировать группы документов для подписания.
В первой строке содержатся целые числа $$$n$$$, $$$d$$$, $$$k$$$ $$$(1 \le n \le 3 \cdot 10^5, \, 1 \le d \le 10^9, \, 1 \le k \le n)$$$ — количество внесённых документов; максимальное количество дней, спустя которое канцелярия должна либо отклонить документ, либо передать его на подпись; минимальное количество документов, которое царь желает подписывать за один раз.
Во второй строке содержатся целые числа $$$t_1, t_2, \ldots, t_n$$$ $$$(0 \le t_1 \le t_2 \le \ldots \le t_n \le 10^9)$$$, $$$t_j$$$ $$$(j = 1, 2, \ldots, n)$$$ — момент времени, в который документ $$$\#j$$$ впервые поступает в канцелярию.
В первой строке выведите два целых числа $$$r$$$ и $$$m$$$ — минимально возможное максимальное количество раз, которое будет отклонён один и тот же документ, и количество групп документов.
Каждая из следующих $$$m$$$ строк должна начинаться с числа $$$g_i$$$ $$$(i = 1, 2, \ldots, m)$$$ — количества документов в группе $$$\#i$$$ и следующих за ним чисел $$$p^{(i)}_1, p^{(i)}_2, \ldots, p^{(i)}_{g_i}$$$ — номеров документов, входящих в группу. Если существует несколько возможных ответов, выведите любой.
10 4 3 3 6 7 13 15 16 16 17 19 19
1 3 3 1 2 3 3 5 7 4 4 9 6 8 10