# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
315999 | semiauto | Sorting (IOI15_sorting) | C++14 | 0 ms | 0 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>
using namespace std;
const int N=5000000;
int n,i,mas1[N],k,m,num1[N],mas[N],num[N],killer,ans1[N],ans2[N],ans,a[N],b[N];
int main()
{
cin>>n;
for (i=0;i<n;i++)
{
scanf("%d",&mas[i]);
num[mas[i]]=i;
num1[mas[i]]=i;
mas1[i]=mas[i];
}
cin>>m;
for (killer=1;killer<=m;killer++)
{
scanf("%d",&a[k]);scanf("%d",&b[k]);
swap(mas[a[k]],mas[b[k]]);
swap(num[mas[a[k]]],num[mas[b[k]]]);k++;
}
for (i=0;i<n;i++)
if (mas[i]!=i)
{
ans1[ans]=i;
ans2[ans]=mas[i];
swap(mas[i],mas[num[i]]);
swap(num[mas[i]],num[mas[num[i]]]);
ans++;
}
cout<<m<<endl;
for (i=0;i<n;i++){mas[i]=mas1[i];num[i]=num1[i];
}
for (i=0;i<m;i++)
{
swap(mas[a[i]],mas[b[i]]);
swap(num[mas[a[i]]],num[mas[b[i]]]);
printf("%d %d\n",num[ans1[i]],num[ans2[i]]);
//cout<<num[ans1[i]]<<" "<<num[ans2[i]]<<endl;
swap(mas[num[ans1[i]]],mas[num[ans2[i]]]);
swap(num[mas[num[ans1[i]]]],num[mas[num[ans2[i]]]]);
}
return 0;
}