# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
874584 | HuyQuang_re_Zero | Sorting (IOI15_sorting) | C++14 | 148 ms | 39732 KiB |
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 <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "sorting.h"
#define mxn 600005
using namespace std;
int n,i,tg[mxn],p[mxn],pos[mxn],r[mxn],x[mxn],y[mxn],m,visited[mxn],res,a[mxn],b[mxn];
int root(int u) { return (u==r[u]) ? u : r[u]=root(r[u]); }
bool check(int k)
{
for(i=1;i<=n;i++) tg[i]=p[i],r[i]=i;
int comp=n;
for(i=1;i<=k;i++) swap(p[x[i]],p[y[i]]);
for(i=1;i<=n;i++)
if(root(i)!=root(p[i]))
{
r[root(i)]=root(p[i]);
comp--;
}
for(i=1;i<=n;i++) p[i]=tg[i];
return n-comp<=k;
}
int findSwapPairs(int _n,int _p[],int _m,int _x[],int _y[],int a[],int b[])
{
n=_n;
for(i=n;i>=1;i--) p[i]=_p[i-1],p[i]++;
m=_m;
for(i=m;i>=1;i--) x[i]=_x[i-1],y[i]=_y[i-1],x[i]++,y[i]++;
int l=0,r=m;
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid)) r=mid; else l=mid+1;
}
/////////////////////////////////////////////////////////////////////////////
for(i=1;i<=n;i++) tg[i]=p[i];
vector <II> vec;
for(i=1;i<=l;i++) swap(p[x[i]],p[y[i]]);
for(i=1;i<=n;i++)
if(visited[i]==0)
{
int u=i;
while(p[u]!=i)
{
//cerr<<u-1<<" "<<p[u]-1<<'\n';
vec.push_back({ u,p[u] }),u=p[u],visited[u]=1;
}
visited[u]=1;
}
for(i=1;i<=n;i++) vec.push_back({ i,i });
reverse(vec.begin(),vec.end());
for(i=1;i<=n;i++) p[i]=tg[i];
//////////////////////////////////////////////////////////////////////////////////
cerr<<'\n';
for(i=1;i<=n;i++) pos[p[i]]=i;
int res=0;
for(i=1;i<=l;i++)
{
swap(pos[p[x[i]]],pos[p[y[i]]]);
swap(p[x[i]],p[y[i]]);
/*
cout<<x[i]-1<<" "<<y[i]-1<<'\n';
for(int i=1;i<=n;i++) cout<<p[i]-1<<" ";
cout<<'\n';
*/
int u=pos[vec.back().fst],v=pos[vec.back().snd]; vec.pop_back();
swap(pos[p[u]],pos[p[v]]);
swap(p[u],p[v]);
/*
cout<<u-1<<" "<<v-1<<'\n';
for(int i=1;i<=n;i++) cout<<p[i]-1<<" ";
cout<<'\n';*/
a[res]=u-1; b[res]=v-1;
res++;
}
return res;
}
/*
int main()
{
freopen("sorting.inp","r",stdin);
freopen("sorting.out","w",stdout);
cin>>n;
for(i=0;i<n;i++) cin>>p[i];
cin>>m;
for(i=0;i<m;i++) cin>>x[i]>>y[i];
cout<<(res=findSwapPairs(n,p,m,x,y,a,b))<<'\n';
for(i=0;i<res;i++) cout<<a[i]<<" "<<b[i]<<'\n';
}
*/
Compilation message (stderr)
# | 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... |