#include "sorting.h"
#include <iostream>
#include <algorithm>
std::pair<int, int> valuesSorting[600010];
int b[200010];
int curPlace[200010];
bool check(int n, int a[], int cur, int x[], int y[])
{
for (int i = 0; i < n; ++i)
{
a[i] = b[i];
}
for (int i = 0; i <= cur; ++i)
{
std::swap(a[x[i]], a[y[i]]);
}
int cnt = 0;
for (int i = 0; i < n; ++i)
{
while (a[i] != i)
{
int who = a[i];
std::swap(a[i], a[who]);
++cnt;
}
}
if (cnt - 1 > cur)
return 0;
else
return 1;
}
int findSwapPairs(int n, int a[], int m, int x[], int y[], int xans[], int yans[]) {
bool flag = false;
for (int i = 0; i < n; ++i)
{
// std::cout << a[i] << " ";
curPlace[a[i]] = i;
if (a[i] != i)
flag = true;
b[i] = a[i];
}
if (!flag)
return 0;
// std::cout << "\n";
/*
int lowest = -1;
for (int i = 0; i < m; ++i)
{
if (check(n, a, i, x, y))
{
lowest = i;
break;
}
}*/
int lowest = m;
int l = 0, r = m - 1;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (check(n, a, mid, x, y))
{
lowest = std::min(lowest, mid);
r = mid - 1;
}
else
{
l = mid + 1;
}
}
for (int i = 0; i < n; ++i)
{
a[i] = b[i];
}
for (int i = 0; i <= lowest; ++i)
{
std::swap(a[x[i]], a[y[i]]);
}
int cnt = 0;
for (int i = 0; i < n; ++i)
{
while (a[i] != i)
{
valuesSorting[cnt].first = a[i];
valuesSorting[cnt].second = a[a[i]];
int who = a[i];
std::swap(a[i], a[who]);
++cnt;
}
}
for (int i = 0; i < n; ++i)
{
a[i] = b[i];
}
for (int i = 0; i <= lowest; ++i)
{
if (x[i] != y[i])
{
int val1 = a[x[i]], val2 = a[y[i]];
std::swap(a[x[i]], a[y[i]]);
curPlace[val1] = y[i];
curPlace[val2] = x[i];
}
/*
for (int i = 0; i < n; ++i)
{
std::cout << curPlace[i] << " ";
}
std::cout << "\n";*/
if (i >= cnt)
{
xans[i] = 0;
yans[i] = 0;
}
else
{
int one = valuesSorting[i].first;
int two = valuesSorting[i].second;
int curOne = curPlace[one];
int curTwo = curPlace[two];
std::swap(a[curOne], a[curTwo]);
xans[i] = curOne;
yans[i] = curTwo;
curPlace[one] = curTwo;
curPlace[two] = curOne;
}
/*
for (int i = 0; i < n; ++i)
{
std::cout << curPlace[i] << " ";
}
std::cout << "\n";*/
}
/*
std::cout << lowest + 1 << "\n";
for (int i = 0; i <= lowest; ++i)
{
std::cout << x[i] << " " << y[i] << "|\n";
std::cout << xans[i] << " " << yans[i] << "\n";
}
*/
return lowest + 1;
}
