# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
315999 | semiauto | 정렬하기 (IOI15_sorting) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}