Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача F. Z-функция

Задачу добавил: DK

Успешно сдано решений: 2

Задача F. Z-функция

 

Ограничение по времени: 1 секунда

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

Название задачи (англ.):   Z-Function

 

Пусть строка – это некоторая последовательность символов алфавита. Z-функция ("зет-функция") от строки S – это массив Z, каждый элемент которого Z[i] равен наидлиннейшему префиксу подстроки, начинающейся с позиции i в строке S, который одновременно является и префиксом всей строки S. Значение Z-функции в позиции 0 обычно считается не определенным (мы его будем считать равным нулю). Так, значение Z - функции строки "abacaba" равно [0, 0, 1, 0, 3, 0, 1].

Вам дана Z-функция некоторой строки. Приведите пример строки с данной Z-функцией. Поскольку не очень хочется решать задачу о раскраске в 26 цветов, алфавит строки будет почти бесконечным.

 

 

Входной файл.

В первой строке целое число N – длина строки. (1 <= N <= 100000). В следующей строке N чисел Zi, 0 <= Zi <= 1000000, Z0 = 0.

 

Выходной файл.

N целых чисел через пробел – строка над алфавитом [0..100000], Z-функция которой равна Z, или "-1" если такой не существует.

 

Входной файл input.txt

Выходной файл output.txt

7

0 0 1 0 3 0 1

1 2 1 3 1 2 1

3

0 2 0

-1

3

0 10000 0

-1

 

Комментарий. Согласно разъяснению жюри (номер 2) первый и третий тесты не совпадают с соответствующими примерами. Первый тест

 

Входной файл input.txt

Выходной файл output.txt

3

0 2 1

1 1 1

Сдать задачу

Задать вопрос жюри по этой задаче