Processing math: 100%

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


Задача B. AB

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

N школьников из классов А и Б выстроены в ряд. i-й школьник в ряду сказал число ci -- сколько школьников не с его класса стоят левее в ряду. Вам дан перемешанный массив c. Восстановите любое возможное изначальное расположение учеников.
Формат входного файла
В первой строке находится одно целое число N(1<=N<=1.5106). Во второй строке находятся N целых числа x1,x2,...,xN(0<=xi<=N) — перемешанный массив c.
Формат выходного файла
Выведите изначальное расположение учеников в виде строки длины N ---состоящей из символов a и b. Гарантируется, что существует хотя бы одна такая строка. Если есть несколько ответов, выведите любое из них.
Система оценки
Данная задача содержит 9 подзадач, в которых выполняются следующие ограничения:
  1. Примеры из условия. Оценивается в 0 баллов.
  2. N<=105. Гарантируется, что существует ответ при которым нет не одного ученика с B класса. Оценивается в 6 баллов.
  3. N<=20. Оценивается в 10 баллов.
  4. N<=105. Гарантируется, что существует ответ при которым есть не более 2 ученика с B класса. Оценивается в 8 баллов.
  5. N<=105. Гарантируется, что существует строка, что полученный массив для этой строки 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 изначальное расположение школьников, то тогда c1=0,c2=0,c3=2,c4=1. Перемешав можно получить массив [1,0,2,0]. ( Temirlan Satylkhanov )
посмотреть в олимпиаде

Комментарий/решение: