Подразделы

Другие разделы

Дата и время

05/04/2025 21:24:03

Авторизация

Зарегистрироваться
Восстановить пароль

Лето 8

A. URL B. A New Growth Industry C. Раскраска кубиков D. Симпатичные узоры 2 E. Две строки F. Печать G. Гладкие числа

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

Ограничения: время – 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/