#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
const int MAXN=200010, LOG=18;
int n, m, ans;
int A[MAXN], B[MAXN], C[MAXN], D[MAXN];
int posB[MAXN], posC[MAXN], posD[MAXN];
int X[MAXN], Y[MAXN], P[MAXN], Q[MAXN];
int Solve(int k){
for (int i=0; i<n; i++){
B[i]=A[i];
C[i]=A[i];
D[A[i]]=A[i];
}/*
for (int i=0; i<k; i++){
swap(B[X[i]], B[Y[i]]);
// swap(C[X[i]], C[Y[i]]);
}
for (int i=0; i<n; i++){
posB[B[i]]=i;
posC[C[i]]=i;
posD[D[i]]=i;
}
int t=0;
for (int i=0; i<n; i++) if (B[i]!=i){
swap(C[X[t]], C[Y[t]]);
swap(posC[C[X[t]]], posC[C[Y[t]]]);
// cerr<<"C: ";for (int j=0; j<n; j++) cerr<<C[j]<<" \n"[j==n-1];
// cerr<<"posC: ";for (int j=0; j<n; j++) cerr<<posC[j]<<" \n"[j==n-1];
int x=i, y=B[i];
// debug2(x, y)
// debug2(D[x], D[y])
// debug2(posC[D[x]], posC[D[y]])
// cerr<<"\n";
swap(D[x], D[y]);
swap(B[posB[x]], B[posB[y]]);
swap(posB[x], posB[y]);
x=D[x];
y=D[y];
P[t]=posC[x];
Q[t]=posC[y];
t++;
}
return t;*/
int t=0;
for (int i=0; i<n; i++) if (B[i]!=i){
P[t]=B[i];
Q[t]=B[B[i]];
t++;
swap(B[i], B[B[i]]);
}
return t;
}
int findSwapPairs(int _n, int _A[], int _m, int _X[], int _Y[], int _P[], int _Q[]){
n=_n;
for (int i=0; i<n; i++) A[i]=_A[i];
m=_m;
for (int i=0; i<m; i++) X[i]=_X[i], Y[i]=_Y[i];
assert(Solve(m)<=m);
ans=m;
for (int i=0; i<ans; i++) _P[i]=P[i], _Q[i]=Q[i];
return ans;
}
Compilation message
sorting.cpp: In function 'int Solve(int)':
sorting.cpp:20:15: warning: unused parameter 'k' [-Wunused-parameter]
20 | int Solve(int k){
| ~~~~^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
620 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
620 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |