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(tar[x[1]],tar[y[1]]);
swap(s[x[1]],s[y[1]]);
tarp[tar[x[1]]]=x[1];
tarp[tar[y[1]]]=y[1];
}
for(int i=0;i<N;i++){
if(s[i]==tar[i])continue;
int now=tarp[s[i]],ori=i;
while(now!=ori){
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=ori^x[ans+1]^y[ans+1];
if(now==x[ans+1]||now==y[ans+1])now=now^x[ans+1]^y[ans+1];
swap(tar[x[ans+1]],tar[y[ans+1]]);
swap(s[x[ans+1]],s[y[ans+1]]);
tarp[tar[x[ans+1]]]=x[ans+1];
tarp[tar[y[ans+1]]]=y[ans+1];
now=tarp[s[ori]];
}
if(ans>=m)break;
}
for(int i=0;i<n;i++){
//cout<<s[i]<<" "<<tar[i]<<"\n";
if(s[i]!=tar[i])ok=0;
}
//cout<<ok<<"\n";
if(ok==0||ans>m){
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(tar[x[1]],tar[y[1]]);
swap(s[x[1]],s[y[1]]);
tarp[tar[x[1]]]=x[1];
tarp[tar[y[1]]]=y[1];
}
for(int i=0;i<N;i++){
//cout<<s[i]<<" "<<tar[i]<<"\n";
if(s[i]==tar[i])continue;
int now=tarp[s[i]],ori=i;
while(now!=ori){
//cout<<now<<" "<<ori<<"\n";
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=ori^x[ans+1]^y[ans+1];
if(now==x[ans+1]||now==y[ans+1])now=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]]);
tarp[tar[x[ans+1]]]=x[ans+1];
tarp[tar[y[ans+1]]]=y[ans+1];
now=tarp[s[ori]];
}
if(ans>=m)break;
}
for(int i=ans;i<m;i++)Q[i]=0,P[i]=0;
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... |