4-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура
Задача B. AB
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
N школьников из классов А и Б выстроены в ряд. i-й школьник в ряду сказал число ci -- сколько школьников не с его класса стоят левее в ряду. Вам дан перемешанный массив c. Восстановите любое возможное изначальное расположение учеников.
Формат входного файла
В первой строке находится одно целое число N(1<=N<=1.5⋅106).
Во второй строке находятся N целых числа x1,x2,...,xN(0<=xi<=N) — перемешанный массив c.
Формат выходного файла
Выведите изначальное расположение учеников в виде строки длины N ---состоящей из символов a и b. Гарантируется, что существует хотя бы одна такая строка.
Если есть несколько ответов, выведите любое из них.
Система оценки
Данная задача содержит 9 подзадач, в которых выполняются следующие ограничения:
- Примеры из условия. Оценивается в 0 баллов.
- N<=105. Гарантируется, что существует ответ при которым нет не одного ученика с B класса. Оценивается в 6 баллов.
- N<=20. Оценивается в 10 баллов.
- N<=105. Гарантируется, что существует ответ при которым есть не более 2 ученика с B класса. Оценивается в 8 баллов.
- N<=105. Гарантируется, что существует строка, что полученный массив для этой строки c будет равен массиву x без перемешивание. Оценивается в 14 баллов.
- N<=40. Оценивается в 13 баллов.
- N<=2000. Оценивается в 10 баллов.
- N<=300000. Оценивается в 27 баллов.
- 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
)
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.