#include "sorting.h"
#include <iostream>
#include <algorithm>
#include <set>
std::set<int> notPlaced;
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[]) {
for (int i = 0; i < n; ++i)
{
curPlace[a[i]] = i;
b[i] = a[i];
}
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]];
curPlace[val1] = y[i];
curPlace[val2] = x[i];
}
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];
xans[i] = curOne;
yans[i] = curTwo;
curPlace[one] = curTwo;
curPlace[two] = curOne;
}
}
/*
std::cout << lowest + 1 << "\n";
for (int i = 0; i <= lowest; ++i)
{
std::cout << xans[i] << " " << yans[i] << "\n";
}*/
return lowest + 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
23 ms |
508 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
23 ms |
508 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |