# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
395024 | WLZ | Sorting (IOI15_sorting) | C++14 | 190 ms | 21280 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 <bits/stdc++.h>
using namespace std;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
auto check = [&](int k) {
vector<int> s(S, S + N), pos(N);
for (int i = 0; i < k; i++) swap(s[X[i]], s[Y[i]]);
for (int i = 0; i < N; i++) pos[s[i]] = i;
int cnt = 0;
for (int i = 0; i < N; i++) {
if (pos[i] != i) {
cnt++;
pos[s[i]] = pos[i];
swap(s[i], s[pos[i]]);
pos[i] = i;
}
}
return cnt <= k;
};
int lo = 0, hi = N - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (check(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
vector<int> s(S, S + N), pos(N);
for (int i = 0; i < lo; i++) swap(s[X[i]], s[Y[i]]);
for (int i = 0; i < N; i++) pos[s[i]] = i;
vector< pair<int, int> > swaps;
for (int i = 0; i < N; i++) {
if (pos[i] != i) {
pos[s[i]] = pos[i];
swaps.push_back({i, s[i]});
swap(s[i], s[pos[i]]);
pos[i] = i;
}
}
s = vector<int>(S, S + N);
for (int i = 0; i < N; i++) pos[s[i]] = i;
for (int i = 0; i < lo; i++) {
swap(pos[s[X[i]]], pos[s[Y[i]]]);
swap(s[X[i]], s[Y[i]]);
if (i < (int) swaps.size()) P[i] = pos[swaps[i].first], Q[i] = pos[swaps[i].second];
else P[i] = Q[i] = 0;
swap(pos[s[P[i]]], pos[s[Q[i]]]);
swap(s[P[i]], s[Q[i]]);
}
return lo;
}
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... |