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

Задача C. Восстановление строки

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

3 секунды

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

256 мегабайт

Вам дана строка $s$ длины $n$, состоящая из строчных латинских букв и символов `?'. Также, вам даны $m$ условий. Каждое условие описывается тремя целыми числами $l_1$, $l_2$ и $x$, которые означают что подстрока $(s_{l_1} \ldots s_{l_1+x-1})$ должна быть равна подстроке $(s_{l_2} \ldots s_{l_2+x-1})$. Вам нужно заменить каждый символ `?' на строчную латинскую букву так чтобы выполнялись все $m$ условия. Среди всех таких строк, найдите лексикографически минимальную. Строка $a$ лексикографический меньше строки $b$, если

• либо первые $k$ символов этих строк совпадают, а $k + 1$-й символ в $a$ алфавитном порядке идет раньше $k + 1$-го символа строки $b$. Например, $abcdef < abdaaaa$, так как первые два символа совпадают, а третья буква первой строки($c$) в алфавитном порядке идет раньше третьей буквы второй строки($d$).
• либо строка $a$ является префиксом строки $b$. Например, $abc < abcde$.

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

В первой строке находится одно целое число $n(1 <= n <= 300000)$. Во второй строке находится строка $s$, состоящая из $n$ строчных латинских букв и символов `?'. В третьей строке находится одно целое число $m(1 <= m <= 300000)$. В следующих $m$ строках записаны по три целых числа $l_1$, $l_2$ и $x$ $(1 <= l_1, l_2 <= n - x + 1)$, означающие что подстрока $(s_{l_1} \ldots s_{l_1+x-1})$ равна подстроке $(s_{l_2} \ldots s_{l_2+x-1})$.

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

Выведите лексикографически минимальную строку, которая удовлетворяет всем условиям, либо $-1$, если такой строки не существует.

Примеры:

Вход

10
a?b?b???b?
3
1 4 3
7 9 2
3 10 1

Ответ

abbabbbbbb

Вход

6
a????b
5
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1

Ответ

-1

( Narkhan Kamzabek )

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

Разве после соблюдения всех условий нельзя все оставшиеся вопросительные знаки заменить на маленькую "a"?

показать/скрыть код

n = int(input())
s = input()
m = int(input())
data = [list(map(int, input().split())) for i in range(m)]


def union(str1, str2):
    str3 = ""
    for el1, el2 in zip(str1, str2):
        if el1 == "?":
            str3 += el2
        elif el2 == "?":
            str3 += el1
        elif el2 != el1:
            print(-1)
            exit(0)
            # print("wtf", el2, el1, str1, str2)
        else:
            str3 += el2
    return str3


new = list(s)
for i in range(m * 2):
    l1, l2, x = data[i % m]
    new[l1 - 1:l1 + x - 1] = (union(new[l1 - 1:l1 + x - 1], new[l2 - 1:l2 + x - 1]))
    new[l2 - 1:l2 + x - 1] = (union(new[l1 - 1:l1 + x - 1], new[l2 - 1:l2 + x - 1]))

new = "".join(["a" if i == "?" else i for i in new])
print(new)

C++

Copy

Задача интересная