Сделал. Тут вроде несложно. Задача явно memory-bound. Значит число

Question

Сделал. Тут вроде несложно. Задача явно memory-bound. Значит число

операций считать не будем, IO тоже считать не будем (уже посчитали с dd)

Парсинг входных данных по времени ничтожен, так как его время линейно зависит от входа, а выход у нас квадратичный.

Что остаётся? Лепка строк.
Для этого мы N^2 раз будем читать suf, и N^2 раз писать (pref + 1 + suf + 1). Итого N^2 * (2suff + pref + 2) оперативной памяти, suff = pref = 5 (в байтах), итого 17N^2 байтов.

Пропускную способность взял 15 гигабайт/с, не знаю сколько сейчас на современных компах на DDR4, но должно быть около того. Для оценки сойдёт.

На длине входа N = 1e4 (что у нас и есть) имеем
17e8 [байт] / 15e8 [байт/c], что примерно равно 1.2 сек.

Ну в общем вывод такой, что вы уже около теоретического значения маячите, что довольно хорошо!