Межзвёздная экспедиция

Просмотр в формате PDF

Submit solution


Очки: 240
Ограничение по времени: 1.0s
Ограничение по памяти: 64M

Автор:
Problem types
Allowed languages
C++

Для межзвёздного путешествия нужно подготовить m независимых экспедиций к разным звёздным системам. В распоряжении штаба есть n пилотов.

Для каждого пилота известен его уровень устойчивости к космическому стрессу. Для j-го пилота он равен a_j.

Для каждой экспедиции известна её сложность. Для i-й экспедиции она равна b_i.

На каждую экспедицию нужно назначить хотя бы одного пилота, причём один и тот же пилот не может участвовать более чем в одной экспедиции.

Если на экспедицию назначено k пилотов, то нагрузка распределяется между ними, и каждый пилот должен выдерживать не меньше чем b_i / k единиц сложности. Так как уровень устойчивости пилотов и сложность экспедиций — целые числа, это условие эквивалентно следующему:

  • если самый слабый пилот в группе имеет устойчивость x, то группа из k пилотов может быть отправлена в экспедицию сложности b_i тогда и только тогда, когда x * k >= b_i.

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

Если это возможно, выведите одно из подходящих распределений.

Формат ввода

В первой строке записаны два целых числа n и m — количество пилотов и количество экспедиций.

Во второй строке записаны n целых чисел a_1, a_2, ..., a_n — уровни устойчивости пилотов.

В третьей строке записаны m целых чисел b_1, b_2, ..., b_m — сложности экспедиций.

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

Если подходящего распределения не существует, выведите

NO

Иначе выведите

YES

Далее выведите m строк.

В i-й из них сначала выведите число k_i — количество пилотов, назначенных на i-ю экспедицию, а затем k_i различных номеров пилотов, входящих в её команду.

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

Если решений несколько, разрешается вывести любое.

Ограничения

  • 1 <= m <= 20
  • 1 <= n <= 2 * 10^5
  • 1 <= a_j <= 10^9
  • 1 <= b_i <= 10^9

Пример 1

Ввод
5 2
4 3 2 2 1
6 3
Вывод
YES
2 1 2
2 3 4

Пример 2

Ввод
4 3
3 2 2 1
5 4 3
Вывод
NO

Пример 3

Ввод
6 3
7 5 4 3 2 2
8 6 4
Вывод
YES
2 2 3
1 1
2 4 5

Комментарии

Еще нет ни одного комментария.