Codeforces Round 923 (Div. 3) |
---|
Закончено |
Поликарп потерял строку $$$s$$$ из $$$n$$$ строчных латинских букв, но у него остался её след.
Следом строки $$$s$$$ называется массив $$$a$$$ из $$$n$$$ целых чисел, в котором $$$a_i$$$ равен количеству таких $$$j$$$ ($$$j < i$$$), что $$$s_i=s_j$$$. Например, следом строки abracadabra является массив [$$$0, 0, 0, 1, 0, 2, 0, 3, 1, 1, 4$$$].
По заданному следу строки найдите любую строку $$$s$$$, из которой он мог быть получен. Строка $$$s$$$ должна состоять только из строчных латинских букв a-z.
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длину потерянной строки.
Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < n$$$) — след строки. Гарантируется, что для заданного следа существует подходящая строка $$$s$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите строку $$$s$$$, которой соответствует данный след. Если таких строк $$$s$$$ несколько, то выведите любую из них.
Строка $$$s$$$ должна состоять из строчных латинских букв a-z.
Гарантируется, что для каждого набора входных данных ответ существует.
5110 0 0 1 0 2 0 3 1 1 4100 0 0 0 0 1 0 1 1 01080 1 2 3 4 5 6 780 0 0 0 0 0 0 0
abracadabra codeforces a aaaaaaaa dijkstra
Название |
---|