Задача №115218. Разбиение массива
Дан массив \(A = [a_1, a_2, \ldots, a_n]\), содержащий \(n\) натуральных чисел.
Требуется раскрасить элементы массива в два цвета таким образом, чтобы не существовало двух элементов \(x\) и \(y\) одного цвета, таких, что \(x\) нацело делился на \(y\) и выполнялось равенство \(\frac{x}{y} = p\), где \(p\) — простое число. Гарантируется, что такая раскраска существует.
Напомним, что целое число \(p > 1\) называется простым, если оно имеет ровно два делителя: \(1\) и \(p\).
Первая строка содержит одно целое число \(n\) (\(1 \le n \le 100\,000\)) — количество элементов в массиве.
Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^6\)) — элементы массива.
Выведите описание разбиения массива на два множества в следующем формате.
Выведите \(n\) целых чисел, \(i\)-е из которых равняется \(1\), если элемент \(a_i\) надо раскрасить в первый цвет, и \(2\), если элемент \(a_i\) надо раскрасить во второй цвет.
Если существует несколько подходящих раскрасок, вы можете вывести любую из них.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 9 | \(a_i \le 2\) для всех \(i\) | первая ошибка | |
| 2 | 19 | Гарантируется, что все \(a_i\) являются степенями некоторого простого числа \(p\) | первая ошибка | |
| 3 | 12 | \(a_i \le 3\) для всех \(i\) | 1 | первая ошибка |
| 4 | 13 | \(a_i \le 4\) для всех \(i\) | 1, 3 | первая ошибка |
| 5 | 21 | \(n \le 10\) | первая ошибка | |
| 6 | 26 | нет | 1–5 | первая ошибка |
В первом примере есть два элемента первого цвета: \(2\) и \(3\), и два элемента второго цвета: \(1\) и \(4\). Элементы первого цвета не делятся нацело друг на друга. \(4\) нацело делится на \(1\), но их отношение не является простым числом.
4 1 2 3 4
2 1 1 2
1 20
1