#include "sorting.h"
#include <iostream>
#include <algorithm>
#include <set>
std::set<int> notPlaced;
int b[200010];
bool check(int n, int a[], int cur, int x[], int y[])
{
notPlaced.clear();
for (int i = 0; i < n; ++i)
{
a[i] = b[i];
}
for (int i = cur; i >= 0; --i)
{
std::swap(a[x[i]], a[y[i]]);
}
for (int i = 0; i < n; ++i)
{
if (a[i] != i)
notPlaced.insert(i);
}
for (int i = 0; i <= cur; ++i)
{
if (notPlaced.size() > 0)
{
int first = *(notPlaced.begin());
int second = a[first];
std::swap(a[first], a[second]);
if (a[first] == first)
notPlaced.erase(first);
if (a[second] == second)
notPlaced.erase(second);
}
else
{
continue;
}
}
if (notPlaced.size() == 0)
return 1;
else
return 0;
}
int findSwapPairs(int n, int a[], int m, int x[], int y[], int xans[], int yans[]) {
for (int i = 0; i < n; ++i)
{
b[i] = a[i];
}
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;
}
}
notPlaced.clear();
for (int i = 0; i < n; ++i)
{
a[i] = b[i];
}
for (int i = lowest; i >= 0; --i)
{
std::swap(a[x[i]], a[y[i]]);
}
for (int i = 0; i < n; ++i)
{
if (a[i] != i)
notPlaced.insert(i);
}
for (int i = 0; i <= lowest; ++i)
{
if (notPlaced.size() > 0)
{
int first = *(notPlaced.begin());
int second = a[first];
xans[i] = first;
yans[i] = second;
std::swap(a[first], a[second]);
if (a[first] == first)
notPlaced.erase(first);
if (a[second] == second)
notPlaced.erase(second);
}
else
{
xans[i] = 0;
yans[i] = 0;
}
}
/*
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 |
8 ms |
512 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
8 ms |
512 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |