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 <cstdio>
#include "sorting.h"
using namespace std;
int S2[200001], vis[200001];
int perm[200001], inv[200001];
//int N, M;
//int S[200001];
//int X[1000001], Y[1000001];
//int P[1000001], Q[1000001];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
//int findSwapPairs(){
int ss = 0, ee = M, R = 0, now = 0;
while(ss <= ee){
int mid = (ss+ee) / 2;
for(int i=0;i<N;i++){
S2[i] = S[i];
vis[i] = 0;
}
for(int i=now;i<mid;i++){
int tmp = S2[X[i]]; S2[X[i]] = S2[Y[i]]; S2[Y[i]] = tmp;
}
int cnt = 0;
for(int i=0;i<N;i++){
if(vis[i]) continue;
int ii = S2[i];
while(ii != i){
vis[ii] = 1;
cnt++;
ii = S2[ii];
}
}
if(cnt <= mid){
R = mid;
ee = mid - 1;
}else{
now = mid;
for(int i=0;i<N;i++) S[i] = S2[i];
ss = mid + 1;
}
}
for(int i=now;i<R;i++){
int tmp = S[X[i]]; S[X[i]] = S[Y[i]]; S[Y[i]] = tmp;
}
for(int i=0;i<N;i++){
//printf("%d ", S[i]);
vis[i] = 0;
perm[i] = i;
inv[i] = i;
}
//printf("\n");
int cnt = 0;
for(int i=0;i<N;i++){
if(vis[i]) continue;
while(S[i] != i){
vis[S[i]] = 1;
P[cnt] = i; Q[cnt] = S[i];
int nxt = S[i];
S[i] = S[nxt];
S[nxt] = nxt;
cnt++;
}
}
/*
for(int i=0;i<R;i++){
printf("%d %d\n", P[i], Q[i]);
}
*/
for(int i=R-2;i>=0;i--){
int tmp;
int p1 = inv[X[i+1]], q1 = inv[Y[i+1]];
tmp = perm[p1]; perm[p1] = perm[q1]; perm[q1] = tmp;
tmp = inv[p1]; inv[p1] = inv[q1]; inv[q1] = tmp;
P[i] = perm[P[i]]; Q[i] = perm[Q[i]];
}
return R;
}
/*
int main(){
int n;
scanf("%d",&N);
for(int i=0;i<N;i++) scanf("%d", &S[i]);
scanf("%d",&M);
for(int i=0;i<M;i++) scanf("%d%d",&X[i], &Y[i]);
int R = findSwapPairs();
printf("%d\n", R);
for(int i=0;i<R;i++){
printf("%d %d\n", P[i], Q[i]);
}
}
*/
# | 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... |