#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
vector<int> x, y;
vector<int> initPos;
int n;
bool check(vector<pii> test) {
vector<int> pos = initPos;
for (int i = 0; i < test.size(); ++i) {
swap(pos[x[i]],pos[y[i]]);
swap(pos[test[i].first],pos[test[i].second]);
}
for (int i = 0; i < n; ++i) {
if (pos[i] != i)
return false;
}
return true;
}
vector<pii> solve(int m) {
vector<int> pos = initPos;
vector<int> orgPosTo(n), orgPos(n);
set<int> notSorted;
vector<pii> ans;
for (int i = 0; i < n; ++i) {
orgPosTo[i] = i;
}
for (int i = 0;i < m;i++) {
swap(pos[x[i]],pos[y[i]]);
}
for (int i = m - 1; i >=0 ; --i) {
swap(orgPosTo[x[i]],orgPosTo[y[i]]);
}
for (int i = 0; i < n; ++i) {
orgPos[orgPosTo[i]] = i;
}
for (int i = 0; i < n; ++i) {
if (pos[i] != i) notSorted.insert(i);
}
for (int i = 0; i < m; ++i) {
auto it = notSorted.begin();
int j = 0;
swap(orgPosTo[x[i]],orgPosTo[y[i]]);
for (int k = 0; k < n; ++k) {
orgPos[orgPosTo[k]] = k;
}
if (it != notSorted.end()) {
j = *it;
}
int target = pos[j];
notSorted.clear();
for (int k = 0; k < n; ++k) {
if (pos[k] != k) notSorted.insert(k);
}
swap(pos[target],pos[j]);
ans.emplace_back(orgPos[j],orgPos[target]);
}
if (!notSorted.empty()) return {};
if (!check(ans)) exit(5);
return ans;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N;
x.resize(M);
y.resize(M);
initPos.resize(n);
for (int i = 0; i < M; ++i) {
x[i] = X[i];
}
for (int i = 0; i < M; ++i) {
y[i] = Y[i];
}
for (int i = 0; i < n; ++i) {
initPos[i] = S[i];
}
for (int i = 1; i <= M; ++i) {
auto v = solve(i);
if (!v.empty()) {
for (int j = 0; j < v.size(); ++j) {
P[j] = v[j].first;
}
for (int j = 0; j < v.size(); ++j) {
Q[j] = v[j].second;
}
return v.size();
}
}
return {};
}
#if DEBUG
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;
static inline int _read() {
if (_charsNumber < 0) {
exit(1);
}
if (!_charsNumber || _currentChar == _charsNumber) {
_charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
_currentChar = 0;
}
if (_charsNumber <= 0) {
return -1;
}
return _buffer[_currentChar++];
}
static inline int _readInt() {
int x; cin >> x;
return x;
}
int main()
{
_inputFile = fopen("sorting.in", "rb");
_outputFile = fopen("sorting.out", "w");
int N, M;
N = _readInt();
int *S = (int*)malloc(sizeof(int) * (unsigned int)N);
for (int i = 0; i < N; ++i)
S[i] = _readInt();
M = _readInt();
int *X = (int*)malloc(sizeof(int) * (unsigned int)M), *Y = (int*)malloc(sizeof(int) * (unsigned int)M);
for (int i = 0; i < M; ++i) {
X[i] = _readInt();
Y[i] = _readInt();
}
int *P = (int*)malloc(sizeof(int) * (unsigned int)M), *Q = (int*)malloc(sizeof(int) * (unsigned int)M);
int ans = findSwapPairs(N, S, M, X, Y, P, Q);
cout << ans << endl;
for (int i = 0; i < ans; ++i)
cout << P[i] << " " << Q[i] << endl;
return 0;
}
#endif
Compilation message
sorting.cpp: In function 'bool check(std::vector<std::pair<int, int> >)':
sorting.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for (int i = 0; i < test.size(); ++i) {
| ~~^~~~~~~~~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:88:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int j = 0; j < v.size(); ++j) {
| ~~^~~~~~~~~~
sorting.cpp:91:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int j = 0; j < v.size(); ++j) {
| ~~^~~~~~~~~~
sorting.cpp:94:26: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
94 | return v.size();
| ~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
11 ms |
348 KB |
Output is correct |
| 4 |
Correct |
13 ms |
348 KB |
Output is correct |
| 5 |
Correct |
13 ms |
488 KB |
Output is correct |
| 6 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1047 ms |
848 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1047 ms |
848 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
