# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
129522 | johutha | Sorting (IOI15_sorting) | C++14 | 186 ms | 21988 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "sorting.h"
#include <vector>
#include <iostream>
using namespace std;
int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
vector<int> perm(n);
bool bc = true;
for (int i = 0; i < n; i++)
{
perm[i] = S[i];
if (perm[i] != i) bc = false;
}
if (bc) return 0;
vector<int> b = perm;
vector<int> beg = perm;
for (int i = 0; i < n; i++)
{
swap(perm[X[i]], perm[Y[i]]);
}
vector<int> end = perm;
int l = 0;
int r = n;
while (r - l > 1)
{
int m = (l + r)/2;
vector<int> mv = beg;
for (int i = l; i < m; i++)
{
swap(mv[X[i]], mv[Y[i]]);
}
vector<bool> v(n, false);
int ctr = 0;
for (int i = 0; i < n; i++)
{
if (v[i]) continue;
v[i] = true;
int cc = 0;
int cr = i;
while (mv[cr] != i)
{
cc++;
cr = mv[cr];
v[cr] = true;
}
ctr += cc;
}
if (ctr <= m)
{
r = m;
end = mv;
}
else
{
l = m;
beg = mv;
}
}
vector<pair<int,int>> swp;
perm = b;
for (int i = 0; i < n; i++)
{
while (end[i] != i)
{
swp.push_back({end[i], end[end[i]]});
swap(end[i], end[end[i]]);
}
}
vector<int> revind(n);
for (int i = 0; i < n; i++)
{
revind[perm[i]] = i;
}
for (int i = 0; i < r; i++)
{
swap(revind[perm[X[i]]], revind[perm[Y[i]]]);
swap(perm[X[i]], perm[Y[i]]);
if (i < swp.size())
{
Q[i] = revind[swp[i].first];
P[i] = revind[swp[i].second];
swap(revind[swp[i].first], revind[swp[i].second]);
swap(perm[Q[i]], perm[P[i]]);
}
else
{
Q[i] = 0;
P[i] = 0;
}
}
return r;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |