#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
const int maxn = 200000;
const int maxm = 600000;
int n, m;
int S[maxn] , X[maxm] , Y[maxm];
int Fx[maxm] , Fy[maxm];
bool valid(int w){ // can we solve if there are w moves?
//copy
int cp1[maxn]; //f(position) = value
int cp2[maxn]; //f(position) = value
for (int i = 0;i < n;i++){
cp1[i] = S[i];
cp2[i] = S[i]; // copy array
}
for (int i = 0;i < w;i++){
swap (cp1[X[i]] , cp1[Y[i]]); //make all swaps
}
int fp[maxn]; //f(value) = position
int ap[maxn]; //f(value) = position
for (int i = 0;i < n;i++){
ap[cp2[i]] = i; //where the value x is at start
fp[cp1[i]] = i; //where the value x is at end
}
int f[maxn]; //f(position) = position
int fi[maxn]; //inverse f
//where is actually the value that will be in x position at end
for (int i = 0;i < n;i++){ //for each value
f[ ap[i] ] = fp[i]; //ap[i] = start of i value //fp[i] = end of i value
} //f[x]=y means that the value on index x must be set to y
for (int i = 0;i < n;i++){
fi[f[i]] = i;
}
int a = 0;
for (int i = 0;i < w;i++){
swap( cp2[X[i]] , cp2[Y[i]]); //update
swap( f[X[i]] , f[Y[i]]);
ap[ cp2[X[i]] ] = X[i];
ap[ cp2[Y[i]] ] = Y[i];
fi[f[X[i]]] = X[i];
fi[f[Y[i]]] = Y[i];
bool end = false;
while (not end and a < n){
//a =
int a1 = ap[a]; //the item with value a
int a2 = fi[a]; //the value that will finish in a position
if (a1 != a2){
swap( cp2[ a1 ] , cp2 [ a2 ]);
ap[cp2[a1]] = a1;
ap[cp2[a2]] = a2;
Fx[i] = a1;
Fy[i] = a2;
end = true;
}
a ++;
}
if (not end){
Fx[i] = 0;
Fy[i] = 0;
}
}
for (int i = 0;i < n;i++){
if (cp2[i] != i){ return false;}
}
return true;
}
int findSwapPairs(int N, int s[], int M, int x[], int y[], int P[], int Q[]){
//freopen("input.in","r",stdin);
//freopen("output.out","w+",stdout);
// input //
n = N;
m = M;
for (int i = 0;i < n;i++){
S[i] = s[i];
X[i] = x[i];
Y[i] = y[i];
}
/*cin >> n;
for (int i = 0;i < n;i++){
cin >> S[i];
}
cin >> m;
for (int i = 0;i < m;i++){
cin >> X[i] >> Y[i];
}*/
// computing solution = binary search //
int a = -1, b = m+1; //in how many turns is possible to sort sequence
while (a + 1 != b){
int h = (a+b)/2;
//cout << a << ' ' << h << ' ' << b << '\n';
if (valid(h)){ //try to make (a,b) as low as possible
b = h; //settle range
}else{
a = h;
}
}
// showing output //
valid(b);
//cout << b << '\n';
for (int i = 0;i < b;i++){
//cout << Fx[i] << ' ' << Fy[i] << '\n';
P[i] = Fx[i];
Q[i] = Fy[i];
}
}
Compilation message
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:115:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
512 KB |
Integer 21617 violates the range [0, 1799] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
512 KB |
Integer 21617 violates the range [0, 1799] |
| 2 |
Halted |
0 ms |
0 KB |
- |
