Пособие/«Парковка»

#include <iostream>
#include <vector>

using namespace std;

vector<int> par, sz; // создаём вектора par(массив ссылок), sz(массив размеров множеств)
vector<int> gm; // gm[i] = j означает, что максимальный номер места в блоке, содержащем i-ое место, - это x

int get_par(int v) { // get_par(v) возвращает номер блока, к которому принадлежит v-ое место
    if (par[v] == v) { // Если элемент ссылается на самого себя, то это корень, следовательно это искомый ответ
        return v; // возвращаем искомый ответ
    }
    // Одновременно находим корень блока (он в виде дерева), к которому принадлежит предок v и напрямую подвешиваем к этому корню v
    return par[v] = get_par(par[v]);
}

void unite(int a, int b) { // функция, объединяющая 2 блока
    a = get_par(a); // находим корень блока, к которому принадлежит a-ое место
    b = get_par(b); // находим корень множества, к которому принадлежит b-ое место
    if (a == b) return; // Если корни блоков равны, то это означает, что блоки уже объединены
    if (sz[a] > sz[b]) // Если размер блока, в котором корень a, больше размера блока, в котором корень b, то меняем значения в a и b
        swap(a, b);
    par[a] = b; // подвешиваем a к b
    sz[b] += sz[a]; // Увеличиваем размер блока с корнем b на размер блока с корнем a
    gm[b] = max(gm[b], gm[a]); // максимальный номер места, принадлежащего b-ому блоку - это максимум из текущего максимального значения и максимального значения у a-го блока
}

void solve() {
    int n;
    cin >> n; // считываем кол-во мест на парковке
    vector<int> ans(n, -1); // ans[i] = j означает, что i-ая машина встала на j-ое место
    vector<bool> free(n, true); // free[i] = true, если i-ое место свободно
                                // free[i] = false, если i-ое место занято
    sz.resize(n, 1); // изначально размер каждого блока равен 1, так как все блоки состоят из 1-ой места
    par.resize(n);
    // изначально каждый блок состоит из 1-го места, которое является корнем, поэтому ссылается на самого себя
    for (int i = 0; i < n; ++i) {
        par[i] = i;
    }
    gm.resize(n); // изначально каждый блок состоит из 1-го места, номер которого является максимальным во всём блоке
    for (int i = 0; i < n; ++i) {
        gm[i] = i;
    }
    for (int i = 0; i < n; ++i) {
        int idx;
        cin >> idx; // считываем номер места, на которое машина планирует встать
        idx--; // уменьшаем номер места на 1, так как в задаче нумерация идёт с 1, а нам выгоднее, если нумерация будет с 0
        if (free[idx]) { // Если место и так свободно, то просто ставим машину туда (помечаем, что место занято)
            ans[i] = idx; // Указываем, что i-ая машина встаёт на idx-ое место
        } else if (gm[get_par(idx)] < n - 1) { // Если блок, содержащий idx-ое место заканчивается раньше (n - 1)-го места, то машина встанет на 1-ое место после этого блока
            ans[i] = gm[get_par(idx)] + 1;
        } else if (free[0]) { // Если блок, содержащий idx-ое место заканчивается в (n - 1)-ом месте, а 0-ое место свободно, то машина встанет на это свободное место
            ans[i] = 0;
        } else { // Если блок, содержащий idx-ое место заканчивается в (n - 1)-ом месте, а 0-ое место занято, то машина встанет на 1-ое место после блока, содержащего 0-ое место
            ans[i] = gm[get_par(0)] + 1;
        }
        free[ans[i]] = false; // Указываем, что место, на которое встанет i-ая машина теперь занято
        if (ans[i] - 1 >= 0 && !free[ans[i] - 1]) { // Если слева от места, на которое встала машина, есть занятый блок, и место слева не "через границу" (Левое число не должно иметь вид n - 1), то объединяем ans[i]-ое место с левым блоком.
            unite(ans[i] - 1, ans[i]);
        }
        if (ans[i] + 1 < n && !free[ans[i] + 1]) { // Если справа от места, на которое встала машина, есть занятый блок, и место справа не "через границу" (Правое число не должно быть равно 0), то объединяем ans[i]-ое место с правым блоком.
            unite(ans[i], ans[i] + 1);
        }
    }
    for (auto el : ans) { // выводим ответы
        cout << el + 1 <<  ' '; // к каждому ответу нужно прибавить 1, так как в задаче нумерация идёт с 1, а в коде с 0
    }
}

int main() {
    solve();
    return 0;
}