ЗАДАЧА K
Расстановка офицеров
| Имя входного файла: | officers.in |
| Имя выходного файла: | officers.out |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 64 Мб |
Ординарец Тамары Семеновны Иванов-оглы-Писемский очень любил вспоминать случаи из армейской жизни. Однажды, когда Шарик с Печкиным на рыбалку пошли, а Матроскин в огороде работал, Иванов-оглы рассказал дяде Федору и его папе, которые как раз читали книжку по программированию, интересную историю.
«Однажды должны были в нашей части учения военные по информатике пройти. Начальства разного большого понаехало. Даже сам генерал-лейтенант-программист Борис Борисович Бинар приехал. А к учением нужно подготовится. Тем более генерал-программисты народ странный и требования у них странные.
Для учений нужно определить ранг офицеров, которые будут находиться в каждом из N командных пунктов. Командные пункты пронумерованы числам от 1 до N, которые соответствуют расстояниям от командных пунктов до главного военно-командного центра (ГВКЦ). В командных пунктах могут находиться только офицеры двух рангов – 0 и 1, причем в каждом командном пункте могут находиться только офицеры одного ранга.
Более того, Бинар изготовил план учений из M положений, i-ое из которых требует, чтобы количество пунктов с офицерами ранга 1 среди пунктов с номерами с Ai по Bi включительно было не меньше Ci.
Другая бы товарищ полковник в такой ситуации растерялась», – продолжал Иванов-оглы, – «но наша товарищ полковник не такая. Она даже выставила дополнительное требование к расстановке.
Пронумеруем пункты с офицерами с рангом 0 от 1 до P в порядке возрастания расстояния от ГВКЦ, где P – общее количество таких пунктов. Тогда в выходной расстановке пункт 1 должен быть как можно ближе к ГКВЦ. Если таких расстановок несколько, то товарищ полковник хотела минимизировать расстояние от пункта 2 до ГКВЦ и т.д. Вот такая сложная задача, но Тамара Семеновна сделала ее в два счета. А вы сможете повторить ее подвиг?»
Входные данные
Первая строка входного файла содержит два натуральных числа N и M (1 <= N <= 100000, 1 <= M <= 100000). В следующих M строках идет описание положений плана Бинара. В (i+1)-ой строке содержится 3 натуральных числа Ai, Bi, Ci (1 <= Ai <= Bi <= N, 0 <= Ci <= Bi – Ai + 1).
Выходные данные
Если расстановка невозможна, то в единственную строку выходного файла выведите строку “No possible arrangement.” (без кавычек). Иначе выведите единственную строку из N цифр 0 или 1, i-ый символ которого соответствует рангу офицеров в i-ом пункте.
Пример
| officers.in | officers.out |
|---|---|
|
|