4-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура

Задача B. AB

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

$N$ школьников из классов А и Б выстроены в ряд. $i$-й школьник в ряду сказал число $c_i$ -- сколько школьников не с его класса стоят левее в ряду. Вам дан перемешанный массив $c$. Восстановите любое возможное изначальное расположение учеников.

Формат входного файла

В первой строке находится одно целое число $N(1 <= N <= 1.5\cdot 10^6)$. Во второй строке находятся $N$ целых числа $x_1,x_2,...,x_N(0 <= x_i <= N)$ — перемешанный массив $c$.

Формат выходного файла

Выведите изначальное расположение учеников в виде строки длины $N$ ---состоящей из символов $a$ и $b$. Гарантируется, что существует хотя бы одна такая строка. Если есть несколько ответов, выведите любое из них.

Система оценки

Данная задача содержит $9$ подзадач, в которых выполняются следующие ограничения:

1. Примеры из условия. Оценивается в $0$ баллов.
2. $N <= 10^5$. Гарантируется, что существует ответ при которым нет не одного ученика с B класса. Оценивается в $6$ баллов.
3. $N <= 20$. Оценивается в $10$ баллов.
4. $N <= 10^5$. Гарантируется, что существует ответ при которым есть не более 2 ученика с B класса. Оценивается в $8$ баллов.
5. $N <= 10^5$. Гарантируется, что существует строка, что полученный массив для этой строки $c$ будет равен массиву $x$ без перемешивание. Оценивается в $14$ баллов.
6. $N <= 40$. Оценивается в $13$ баллов.
7. $N <= 2000$. Оценивается в $10$ баллов.
8. $N <= 300000$. Оценивается в $27$ баллов.
9. $N <= 1500000$. Оценивается в $12$ баллов.

Примеры:

Вход

4
1 0 2 0

Ответ

bbab

Вход

5
0 0 2 1 3

Ответ

bbaba

Замечание

Если $bbab$ изначальное расположение школьников, то тогда $c_1 = 0, c_2 = 0, c_3 = 2, c_4 = 1$. Перемешав можно получить массив [1,0,2,0]. ( Temirlan Satylkhanov )