Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
248. Раскраска кубиков
Задачи на идеюТехника программирования, моделирование
Жадные алгоритмы
Олимпиадные задачи на русском языке
| 02/07/2007 | Лето 2007 дорешивание ( 8C) |
| 18/07/2007 | Лето 2007 - 8 (C) |
| 25/10/2008 | Занятие 6 (C) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (2)
На день рождения Пете подарили коробку кубиков. На каждом кубике написано некоторое целое число. Петя выложил все `n` своих кубиков в ряд, так что числа на кубиках оказались расположены в некотором порядке `a_1,\ a_2,\ …,\ a_n`.
Теперь он хочет раскрасить кубики в разные цвета таким образом, чтобы для каждого цвета последовательность чисел на кубиках этого цвета была строго возрастающей. То есть, если кубики с номерами `i_1,\ i_2,\ …,\ i_k` покрашены в один цвет, то `a_{i_1}\ <\ a_{i_2}\ <\ …\ <\ a_{i_k}`.
Петя хочет использовать как можно меньше цветов. Помогите ему!
Первая строка входного файла содержит число `n` – количество кубиков у Пети `(1\ ≤\ n\ ≤\ 250000)`. Затем следует `n` чисел, разделенных пробелами и/или переводами строки – `a_1,\ a_2,\ …,\ a_n`.
На первой строке выходного файла выведите число `L` – наименьшее количество цветов, которое потребуется Пете. На следующей строке выведите `n` чисел из диапазона от 1 до `L` – цвета, в которые Петя должен покрасить кубики.
Пример ввода
5 1 2 4 3 5
Пример вывода
2 1 1 1 2 2
