06/04/2025 16:12:09

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

248. Раскраска кубиков

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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

Источник: http://neerc.ifmo.ru/school/archive/

02/07/2007	Лето 2007 дорешивание ( 8C)
18/07/2007	Лето 2007 - 8 (C)
25/10/2008	Занятие 6 (C)