# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
432513 | snasibov05 | Sorting (IOI15_sorting) | C++14 | 1065 ms | 76888 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 <cassert>
#include <algorithm>
using namespace std;
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
vector<vector<int>> v(m+1, vector<int>(n));
vector<vector<int>> idx(m+1, vector<int>(n));
for (int i = 0; i < n; ++i) {
v[0][i] = s[i];
idx[0][s[i]] = i;
}
if (is_sorted(v[0].begin(), v[0].end())) return 0;
for (int i = 1; i <= m; ++i) {
v[i] = v[i-1];
idx[i] = idx[i-1];
swap(idx[i][v[i][x[i-1]]], idx[i][v[i][y[i-1]]]);
swap(v[i][x[i-1]], v[i][y[i-1]]);
vector<int> final = idx[i];
vector<int> arr = v[i];
vector<pii> swaps;
for (int j = 0; j < n; ++j) {
if (final[j] == j) continue;
int k = final[j];
swaps.pb({j, k});
final[arr[j]] = k;
arr[k] = arr[j];
arr[j] = j;
}
if (swaps.size() > i) continue;
arr = v[i];
for (int j = 0; j < m; ++j) {
p[i] = q[i] = 0;
}
int k = swaps.size();
for (int l = 1; l <= k; ++l){
if (is_sorted(v[l].begin(), v[l].end())) return l;
int a = idx[l][arr[swaps[l-1].f]];
int b = idx[l][arr[swaps[l-1].s]];
p[l-1] = a, q[l-1] = b;
swap(idx[l][arr[swaps[l-1].f]], idx[l][arr[swaps[l-1].s]]);
swap(v[l][a], v[l][b]);
swap(arr[swaps[l-1].f], arr[swaps[l-1].s]);
if (is_sorted(v[l].begin(), v[l].end())) return l;
for (int j = l+1; j <= i; ++j) {
v[j] = v[j-1];
idx[j] = idx[j-1];
swap(idx[j][v[j][x[j-1]]], idx[j][v[j][y[j-1]]]);
swap(v[j][x[j-1]], v[j][y[j-1]]);
}
}
return i;
}
assert(false);
}
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... |