#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
//static FILE *_inputFile, *_outputFile;
int n;
vector<pair<int,int> > v;
int p[200001],pos[200001];
void swaps()
{
//for(int i=0;i<n;i++)
// fprintf(_outputFile,"%d ",p[i]);
// fprintf(_outputFile,"\n");
for(int i=0; i<n; i++)
pos[p[i]]=i;
for(int i=0; i<n; i++)
{
if(p[i]!=i)
{
v.push_back({i,p[i]});
//fprintf(_outputFile, "%d %d\n", i,p[i]);
pos[p[i]]=pos[i];
swap(p[i],p[pos[i]]);
pos[i]=pos[p[i]];
}
}
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[],int P[],int Q[])
{
n=N;
int ans=0;
int l=0,r=M;
while(l<=r)
{
int m=(l+r)/2;
for(int i=0; i<n; i++)
p[i]=S[i];
for(int i=0; i<m; i++)
swap(p[X[i]],p[Y[i]]);
v.clear();
swaps();
if(v.size()<=m)
{
r=m-1;
ans=m;
}
else l=m+1;
}
for(int i=0; i<n; i++)
p[i]=S[i];
for(int i=0; i<ans; i++)
swap(p[X[i]],p[Y[i]]);
v.clear();
swaps();
//for(int i=0;i<v.size();i++)
// fprintf(_outputFile, "%d %d ", v[i].first, v[i].second);
for(int i=0;i<M;i++)
P[i]=Q[i]=0;
for(int i=0;i<n;i++)
p[i]=S[i];
for(int i=0; i<n; i++)
pos[p[i]]=i;
for(int i=0; i<ans; i++)
{
pos[p[Y[i]]]=X[i];
pos[p[X[i]]]=Y[i];
swap(p[X[i]],p[Y[i]]);
if(i<v.size())
{
P[i]=pos[v[i].first];
Q[i]=pos[v[i].second];
}
if(P[i]>Q[i])swap(P[i],Q[i]);
pos[p[P[i]]]=Q[i];
pos[p[Q[i]]]=P[i];
swap(p[P[i]],p[Q[i]]);
}
return ans;
}
/*int nn,mm;
int ss[200001];
int xx[200001],yy[200001];
int pp[200001],qq[200001];
int gg[200001];
int main()
{
while(1)
{
nn=6;
mm=3;
for(int i=0;i<nn;i++)
ss[i]=i;
for(int i=0;i<mm;i++)
{
int x,y;
x=rand()%6;
y=rand()%6;
//cin>>x>>y;
//cin>>xx[i]>>yy[i];
swap(ss[x],ss[y]);
xx[mm-i-1]=rand()%6;
yy[mm-i-1]=rand()%6;
swap(ss[xx[i]],ss[yy[i]]);
}
for(int i=0;i<nn;i++)
gg[i]=ss[i];
int ans=findSwapPairs(nn,ss,mm,xx,yy,pp,qq);
//cout<<ans<<endl;
for(int i=0;i<ans;i++)
{
swap(ss[xx[i]],ss[yy[i]]);
//cout<<pp[i]<<" "<<qq[i]<<endl;
swap(ss[pp[i]],ss[qq[i]]);
}
for(int i=0;i<nn;i++)
{
if(ss[i]!=i)
{
cout<<nn<<endl;
for(int j=0;j<nn;j++)
cout<<gg[j]<<" ";
cout<<endl;
for(int j=0;j<mm;j++)
cout<<xx[j]<<" "<<yy[j]<<endl;
return 0;
}
}
}
}
*/
# | 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... |