Олимпиадный тренинг

Задача . Парковка


Задача

Темы:

Специально для \(n\) сотрудников ИТМО, пользующихся личными автомобилями, планируется открыть парковку. На парковке должно быть ровно \(n\) парковочных мест, каждому сотруднику должно достаться свое место.

Для экономии мест парковка будет разбита на несколько <<рядов>>. Места в каждом ряду нумеруются от \(1\) (самое дальнее от въезда) до длины ряда (самое ближнее ко въезду), и дальние места недоступны, пока не освободятся все более ближние.

Для каждого сотрудника известно, в какое время он приезжает, и в какое время заканчивает работу. Так как сотрудники ИТМО  — очень трудолюбивые люди, каждый из них приезжает на работу в один день, а уезжает уже в следующий. Для каждого известно время, в которое он приезжает на работу \(t^\mathrm{in}_i\), и время, в которое он уезжает на следующий день \(t^\mathrm{out}_i\). Требуется назначить места сотрудникам так, чтобы никому из них не понадобилось ждать

  • появления доступного парковочного места, когда он приезжает;

  • возможности выехать, когда он заканчивает работу.

Более формально, если сотрудникам \(i\) и \(j\) назначены места \(p_i\) и \(p_j\) в одном ряду, и \(p_i < p_j\), должно выполняться \(t^\mathrm{in}_i < t^\mathrm{in}_j\) и \(t^\mathrm{out}_i > t^\mathrm{out}_j\).

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

Формат входных данных

В первой строке ввода дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют описания наборов входных данных.

В первой строке описания набора входных данных дано единственное целое число \(n\) — количество сотрудников, которых необходимо разместить на парковке.

Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\).

Во второй строке набора входных данных через пробел перечислены \(n\) целых чисел \(t^\mathrm{in}_i\) — времена приезда сотрудников на работу (\(1 \le t^\mathrm{in}_i \le 10^9\)). В третьей строке в том же формате перечислены \(n\) целых чисел \(t^\mathrm{out}_i\) — времена отъезда сотрудников (\(1 \le t^\mathrm{out}_i \le 10^9\)).

Формат выходных данных
Выведите ответ на задачу для каждого набора входных данных в том порядке, в котором они перечислены во вводе.

В первой строке ответа выведите единственное целое число \(k\) — минимальное необходимое количество рядов. В \(i\)-й из следующих \(k\) строк выведите описание \(i\)-го ряда: первое число в строке \(\mathrm{cnt}_i\) должно быть равно количеству мест в ряду, после чего должны следовать \(\mathrm{cnt}_i\) целых чисел от \(1\) до \(n\) — номера сотрудников, занимающих места этого ряда, в порядке от самого глубокого к самому ближнему ко въезду.

Если существует несколько различных ответов, минимизирующих \(k\), выведите любой из них.

 

Примеры
Входные данныеВыходные данные
1 4
2
1 2
3 4
3
5 7 6
4 3 1
4
1 2 3 4
8 7 5 6
2
3 1
2 5
2
1 1 
1 2 
2
2 1 3 
1 2 
2
3 1 2 3 
1 4 
1
2 2 1 

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w644
Комментарий учителя