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

Есеп C. Cөзді табу

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

3 seconds

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

256 megabytes

Сізге ұзындығы $n$ болатын, кіші латын әріптері және `?' таңбаларынан тұратын $s$ сөзі беріледі. Сондай-ақ, сізде $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$ символ бірдей , ал $a$ның $k + 1$-ші символы алфавитте $b$ның $k + 1$-ші символын ерте болады. Мысалы, $abcdef < abdaaaa$, бірінші екі символдары бірдей, ал бірінші сөздің үшінші әрпі ('$c$') екінші сөздің үшінші әрпінен ('$d$') алфавитте ерте кездеседі.
• немесе $a$ сөзі $b$ сөзінің префиксі. Мысалы, $abc < abcde$.

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

Бірінші жолда $n(1 <= n <= 300000)$ бүтін саны берілген. Екінші жолда ұзындығы $n$ болатын $s$ сөзі берілген. Үшінші жолда $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

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