#include<bits/stdc++.h>
#include "sorting.h"
using namespace std;
#define pii pair<int,int>
vector<pii> swaps;
vector<pii> evil;
vector<int> arr;
int getMedian(vector<int> arr){
sort(arr.begin(),arr.end());
return arr[(arr.size()-1)/2];
}
void doSwap(int a, int b){
// if(min(a,b) == 0 && max(a,b) == 1 && evil[0].second == 1){
// a = 0;
// b = 0;
// }
swaps.push_back({a,b});
swap(arr[a], arr[b]);
swap(arr[evil[swaps.size()-1].first], arr[evil[swaps.size()-1].second]);
}
void quicksort(int l, int r){
if(l == r) return;
vector<int> cur;
for(int i = l; i <= r; i++){
cur.push_back(arr[i]);
}
int mid = l+((cur.size()-1)/2);
int med = getMedian(cur);
int rpt = r;
for(int i = l; i <= mid; i++){
while(rpt > cur.size()/2 && arr[rpt] > med){
rpt--;
}
if(arr[i] > med){
doSwap(i,rpt);
rpt--;
}
}
quicksort(l, mid);
quicksort(mid+1, r);
}
int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int ops = 0;
arr.resize(n);
map<int,int> pos;
for(int i = 0; i < n; i++){
arr[i] = S[i];
pos[arr[i]] = i;
}
evil.resize(M);
for(int i = 0; i < M; i++){
evil[i] = {X[i], Y[i]};
}
// ST 1 & 2
if(Y[0] == 0){
if(n == 1){
return 0;
}
if(n == 2){
if(arr[0] == 1 && arr[1] == 0){
P[0] = 0;
Q[0] = 1;
return 1;
}else{
return 0;
}
}
quicksort(0,n-1);
for(int i = 0; i < swaps.size(); i++){
P[i] = swaps[i].first;
Q[i] = swaps[i].second;
}
return swaps.size();
}
if(n == 1){
return 0;
}
if(n == 2){
if(arr[0] == 1 && arr[1] == 0){
return 1;
}else{
return 0;
}
}
doSwap(0, pos[1]);
for(int i = 0; i < n; i++){
pos[arr[i]] = i;
}
if(arr[0] != 0){
doSwap(0, pos[0]);
}else{
doSwap(1, pos[0]);
}
quicksort(2,n-1);
if(arr[0] == 1 && arr[1] == 0){
if(X[0] == 0 && Y[0] == 1){
doSwap(0,0);
}else{
doSwap(0,1);
}
}
for(int i = 0; i < swaps.size(); i++){
P[i] = swaps[i].first;
Q[i] = swaps[i].second;
}
return swaps.size();
}
