1. Идея

Нужно зашифровать строку, разбивая её на блоки длины m.

Для каждого блока задана перестановка p длины m. По условию буква, которая стояла в исходном блоке на позиции p[j], после шифрования окажется на позиции j.

Значит, если мы строим новый блок слева направо, то на j-е место нужно поставить символ из позиции p[j] исходного блока.

Именно это и делает эталонное решение: для каждого блока оно последовательно добавляет символы в порядке p[1], p[2], ..., p[m].

2. Наблюдения

Наблюдение 1

Перестановка уже задаёт готовое правило для формирования зашифрованного блока.

Если блок равен block, то его зашифрованный вариант получается так:

• первый символ результата берём из block[p[1]]
• второй — из block[p[2]]
• ...
• j-й — из block[p[j]]

Здесь в условии позиции нумеруются с 1, а в программах строки индексируются с 0, поэтому часто используется p[j] - 1.

Наблюдение 2

Блоки никак не зависят друг от друга.

Можно отдельно обработать каждый фрагмент строки длины m, получить его шифрованную версию и просто дописать в ответ.

Наблюдение 3

Не нужно восстанавливать никакую обратную перестановку.

Иногда в задачах про перестановки нужно думать, куда переходит каждый символ. Но здесь правило уже записано в удобном виде: символ на позиции p[j] исходного блока становится символом на позиции j нового блока. Значит, новый блок можно строить напрямую.

3. Алгоритм

1. Считываем m.
2. Считываем перестановку p длины m.
3. Считываем строку s.
4. Идём по строке блоками длины m:
   • пусть start — начало текущего блока;
   • для каждого j от 0 до m - 1:
     • добавляем в ответ символ s[start + p[j] - 1] в Python;
     • или s[start + p[j]], если в C++ предварительно уменьшили все p[j] на 1.
5. Выводим полученную строку.

4. Почему это работает

Рассмотрим любой блок строки, начинающийся с позиции start.

По условию задачи для каждого j:

• символ, стоявший в исходном блоке на позиции p[j], должен оказаться на позиции j после шифрования.

Если считать позиции внутри блока от 1, то символ на позиции p[j] блока — это символ строки s[start + p[j] - 1].

Алгоритм именно этот символ и ставит на очередную позицию нового блока. Он делает это для всех j от 1 до m, то есть полностью формирует зашифрованный блок строго по правилу из условия.

Так как все блоки обрабатываются независимо и одинаково, вся итоговая строка тоже будет зашифрована правильно.

5. Сложность

Пусть длина строки равна n.

• Каждый символ строки добавляется в ответ ровно один раз.
• Поэтому время работы равно O(n).
• Дополнительная память для ответа — `O(n)``.

Перестановка занимает O(m) памяти, что несущественно по сравнению с длиной строки.

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int m;
    cin >> m;

    vector<int> p(m);
    for (int i = 0; i < m; i++) {
        cin >> p[i];
        p[i]--;
    }

    string s;
    cin >> s;

    string result;
    result.reserve(s.size());

    for (int start = 0; start < (int)s.size(); start += m) {
        for (int j = 0; j < m; j++) {
            result += s[start + p[j]];
        }
    }

    cout << result << '\n';
    return 0;
}

7. Код на Python 3

m = int(input())
p = list(map(int, input().split()))
s = input()

res = []

for start in range(0, len(s), m):
    for j in range(m):
        res.append(s[start + p[j] - 1])

print(''.join(res))