1. Идея

Нужно восстановить исходное слово по зашифрованному.

Шифрование работало так:

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

Значит, если у нас уже есть зашифрованный блок, то можно сделать обратное действие:

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

Именно это и нужно делать для каждого блока.

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

Рассмотрим один блок длины m.

По условию при шифровании:

• в зашифрованный блок на позицию j записали символ из исходного блока с позиции p[j].

Пусть зашифрованный блок хранится в строке s[start ... start + m - 1].

Тогда:

• s[start + j] — это символ, который пришёл из позиции p[j] исходного блока.

Значит, при восстановлении надо сделать:

• block[p[j] - 1] = s[start + j]

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

3. Алгоритм

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

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

Докажем, что алгоритм правильно восстанавливает каждый блок.

По правилу шифрования для каждого j:

• символ из исходной позиции p[j] попадает в зашифрованную позицию j.

Обозначим:

• orig — исходный блок,
• enc — зашифрованный блок.

Тогда верно:

• enc[j] = orig[p[j] - 1]

Нужно получить orig.

Если взять символ enc[j], то мы точно знаем, что в исходном блоке он стоял на позиции p[j] - 1. Поэтому при расшифровке надо выполнить:

• orig[p[j] - 1] = enc[j]

Именно это и делает алгоритм.

Так как p — перестановка, все значения p[j] различны и покрывают все позиции от 1 до m. Значит:

• каждая позиция исходного блока будет заполнена ровно один раз;
• ни одна позиция не потеряется;
• блок восстановится однозначно.

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

5. Сложность

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

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

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];
    }

    string s;
    cin >> s;

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

    for (int start = 0; start < (int)s.size(); start += m) {
        string block(m, ' ');
        for (int j = 0; j < m; j++) {
            block[p[j] - 1] = s[start + j];
        }
        result += block;
    }

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

7. Код на Python 3

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

parts = []

for start in range(0, len(s), m):
    block = [''] * m
    for j in range(m):
        block[p[j] - 1] = s[start + j]
    parts.append(''.join(block))

print(''.join(parts))