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<bits/stdc++.h>
using namespace std;
int tar[200010],tarp[200010],n,x[200010],y[200010],s[200010];
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n=N;
for(int i=0;i<M;i++){
x[i+1]=X[i];
y[i+1]=Y[i];
}
int l=0,r=M;
while(l!=r){
int m=(l+r)>>1,ok=1;
//cout<<l<<" "<<r<<" "<<m<<"\n";
for(int i=0;i<N;i++){
tar[i]=i;
s[i]=S[i];
}
for(int i=m;i>0;i--){
swap(tar[x[i]],tar[y[i]]);
}
for(int i=0;i<N;i++){
tarp[tar[i]]=i;
}
int ans=0;
if(m!=0){
swap(tarp[tar[x[1]]],tarp[tar[y[1]]]);
swap(tar[x[1]],tar[y[1]]);
swap(s[x[1]],s[y[1]]);
}
for(int i=0;i<N;i++){
if(s[i]==tar[i])continue;
int now=tarp[s[i]],ori=i;
while(s[now]!=tar[now]){
P[ans]=now;
Q[ans]=ori;
swap(s[now],s[ori]);
ans++;
if(ans>=m)break;
if(ori==x[ans+1]||ori==y[ans+1])ori^=x[ans+1]^y[ans+1];
if(now==x[ans+1]||now==y[ans+1])now^=x[ans+1]^y[ans+1];
swap(tarp[tar[x[ans+1]]],tarp[tar[y[ans+1]]]);
swap(tar[x[ans+1]],tar[y[ans+1]]);
swap(s[x[ans+1]],s[y[ans+1]]);
now=tarp[s[now]];
}
if(ans>=m)break;
}
for(int i=0;i<n;i++){
//cout<<s[i]<<" "<<tar[i]<<"\n";
if(s[i]!=tar[i])ok=0;
}
if(ok==0){
l=m+1;
}else{
r=m;
}
}
int m=l;
for(int i=0;i<N;i++){
tar[i]=i;
s[i]=S[i];
}
for(int i=m;i>0;i--){
swap(tar[x[i]],tar[y[i]]);
}
for(int i=0;i<N;i++){
tarp[tar[i]]=i;
}
int ans=0;
if(m!=0){
swap(tarp[tar[x[1]]],tarp[tar[y[1]]]);
swap(tar[x[1]],tar[y[1]]);
swap(s[x[1]],s[y[1]]);
}
for(int i=0;i<N;i++){
if(s[i]==tar[i])continue;
int now=tarp[s[i]],ori=i;
while(s[now]!=tar[now]){
P[ans]=now;
Q[ans]=ori;
swap(s[now],s[ori]);
ans++;
if(ori==x[ans+1]||ori==y[ans+1])ori^=x[ans+1]^y[ans+1];
if(now==x[ans+1]||now==y[ans+1])now^=x[ans+1]^y[ans+1];
swap(tarp[tar[x[ans+1]]],tarp[tar[y[ans+1]]]);
swap(tar[x[ans+1]],tar[y[ans+1]]);
swap(s[x[ans+1]],s[y[ans+1]]);
now=tarp[s[now]];
}
}
return l;
}
# | 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... |