1. Идея

Нужно переставить элементы массива так, чтобы:

• сначала шли все числа, меньшие p;
• потом все числа, не меньшие p;
• при этом внутри каждой группы порядок должен остаться таким же, как был изначально.

Это означает, что удобно пройти по массиву один раз и разложить элементы в два отдельных списка:

• less — для элементов < p;
• greater_equal — для элементов >= p.

После этого достаточно вывести сначала less, затем greater_equal.

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

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

   Например, если массив равен 3 1 4 1 5, а p = 3, то:

   • элементы < 3 — это 1 1;
   • элементы >= 3 — это 3 4 5.

   Именно в таком порядке их и нужно вывести.

2. Если идти по массиву слева направо и добавлять каждый элемент в подходящий список, то порядок автоматически сохранится.

3. Никаких сложных структур данных не нужно. Достаточно двух обычных массивов или списков.

3. Алгоритм

1. Считать n.
2. Считать массив a из n чисел.
3. Считать порог p.
4. Создать два пустых списка:
   • less
   • greater_equal
5. Для каждого элемента x массива:
   • если x < p, добавить x в less;
   • иначе добавить x в greater_equal.
6. Вывести сначала все элементы less, затем все элементы greater_equal.

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

Рассмотрим любой элемент массива.

• Если он меньше p, по условию он должен оказаться в первой группе. Алгоритм именно туда его и помещает.
• Если он не меньше p, по условию он должен оказаться во второй группе. Алгоритм помещает его во вторую группу.

Значит, каждый элемент попадёт ровно в ту часть ответа, в которую должен.

Теперь разберёмся с порядком.

Мы просматриваем массив слева направо. Если два элемента x и y относятся к одной и той же группе, и x стоял раньше y в исходном массиве, то:

• x будет обработан раньше;
• значит, он раньше будет добавлен в соответствующий список.

Следовательно, внутри less порядок сохраняется, и внутри greater_equal тоже сохраняется.

Когда мы выводим less, а затем greater_equal, получаем ровно требуемое разбиение.

5. Сложность

• Время работы: O(n), потому что массив просматривается один раз.
• Дополнительная память: O(n), потому что элементы хранятся в двух списках.

6. Код на C++17

#include <iostream>
#include <vector>
using namespace std;

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

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    long long p;
    cin >> p;

    vector<long long> less;
    vector<long long> greater_equal;

    for (int i = 0; i < n; i++) {
        if (a[i] < p) {
            less.push_back(a[i]);
        } else {
            greater_equal.push_back(a[i]);
        }
    }

    bool first = true;
    for (long long x : less) {
        if (!first) cout << ' ';
        cout << x;
        first = false;
    }
    for (long long x : greater_equal) {
        if (!first) cout << ' ';
        cout << x;
        first = false;
    }
    cout << '\n';

    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))
p = int(input())

less = []
greater_equal = []

for x in a:
    if x < p:
        less.append(x)
    else:
        greater_equal.append(x)

result = less + greater_equal
print(*result)