Question

Дан массив из N различных натуральных чисел от 1 до N. Сортировка массива по возрастанию «пузырьком» работает следующим образом. Сначала сравниваются первый и второй элемент, и, если первый больше второго, то они меняются местами. Затем та же процедура производится со вторым и третьим элементом, …, с предпоследним и последним. Затем эта процедура снова повторяется с первым и вторым, со вторым и третьим, …, с предпоследним и последним элементами. И так (N−1) раз. Сортировка «с конфеткой» выполняется по тем же правилам, но дополнительно задан список пар чисел, которые не меняются друг с другом ни при каких условиях (в таком случае сортирующий получает конфетку за то, что пропускает соответствующий обмен). Например, наличие в списке пары (4,1) обозначает, что если в какой-то момент рядом окажутся числа 4 и 1, и по алгоритму сортировки их нужно будет поменять местами, то обмена не произойдет, а сортирующий получит конфетку.
Входные данные
4
1 4 2 3
2
4 3
1 2
Выходные данные
1 2 4 3

Answer 1

#include <iostream>

#include <vector>

#include <cmath>

#include <set>

using namespace std;

void swap(int *a, int *b){

   int temp = *a;

   *a = *b;

   *b = temp;

}

signed main() {

   set<pair<int,int>> s;

   int n;

   cin >> n;

   vector<int> a(n);

   for(int &i:a)

       cin >> i;

   int m;

   cin >> m;

   while(m--){

       int x,y;

       cin >> x >> y;

       s.insert({x,y});

       s.insert({y,x});

   }

   for(int i = 0; i < n; i++)

       for(int j = 0; j < n - i - 1; j++)

           if(a[j] > a[j+1] && s.find({a[j],a[j+1]}) == s.end())

               swap(a[j],a[j+1]);

   for(int &i:a)

       cout << i << " ";

}