| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 65562 | tugushka | Sorting (IOI15_sorting) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#define M 600001
using namespace std;
int n, m, a[200002];
int x[M], y[M], p[M], q[M], tmp[M];
int p1[M];
void print(){
for(int i = 0 ; i < n ; i++)
cout << tmp[i] << ' ';
cout << endl;
for(int i = 0 ; i < n ; i++)
cout << p1[i] << ' ';
cout << endl;
}
bool check( int k ){
for(int i = 0 ; i < n ; i++)
tmp[i] = a[i];
for(int i = 0 ; i < k ; i++)
swap( tmp[ x[i] ], tmp[ y[i] ] );
// p1[i] -> i-r toonii bairlal
for(int i = 0 ; i < n ; i++)
p1[ tmp[i] ] = i;
// cout << k << endl;
// print();
// cout << "----------------\n";
int now = 0;
for(int i = 0 ; i < n ; i++){
if( now+1 > k ) break;
if( tmp[i] == i ) continue;
int f = p1[i];
p[now] = i;
q[now] = f;
p1[ tmp[i] ] = f;
p1[ i ] = i;
swap( tmp[i], tmp[f] );
now++;
// cout << f << ' ' << i << endl;
// print();
// cout << "****************\n";
}
// print();
for(int i = 0 ; i < n ; i++)
if( tmp[i] != i ) return 0;
while( now < k ) p[now] = q[now] = 0, now++;
return 1;
}
int main()
{
// freopen("sorting.in","r", stdin);
// freopen("out.txt","w",stdout);
scanf("%d", &n);
for(int i = 0 ; i < n ; i++)
scanf("%d", &a[i]);
scanf("%d", &m);
for(int i = 0 ; i < m ; i++)
scanf("%d %d", &x[i], &y[i]);
/*
int res;
for(int i = 0 ; i <= m ; i++)
if( check(i) ){
res = i;
break;
}
*/
int l = 0, r = m, res;
while( l < r ){
int mid = (l+r) / 2;
bool f = check( mid );
// cout << "END : " << f << endl;
// cout << "#################\n";
if( f ) r = mid, res = mid;
else l = mid+1;
}
check( res );
printf("%d\n", res);
for(int i = 0 ; i < res ; i++)
printf("%d %d\n", p[i], q[i]);
}