| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 20233 | khuder | 정렬하기 (IOI15_sorting) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <cstdio>
#include "sorting.h"
using namespace std;
int n, m;
int s[200001], x[300001], y[300001], bob[200001], ax[300001], ay[300001], pos[200001];
int p[300001], q[300001], ansR;
void readData(){
scanf("%d", &n);
int i;
for(i=0;i<n;i++){
scanf("%d", &s[i]);
bob[i]=s[i];
}
scanf("%d", &m);
for(i=0;i<m;i++){
scanf("%d%d", &x[i], &y[i]);
}
}
void initBob(){
for(int i=0;i<n;i++)
bob[i]=s[i];
}
void swap(int *a, int *b){
int temp=*a;
*a=*b;
*b=temp;
}
void swapBob(int t){
for(int i=0;i<t;i++){
swap(&bob[x[i]], &bob[y[i]]);
}
}
void printA(int *arr){
for(int i=0;i<n;i++)
cout << arr[i] << " ";
cout << endl;
}
void doBob(int t){
initBob();
swapBob(t);
}
int swapCount(){
int sC=0;
for(int i=0;i<n;i++){
while(bob[i]!=i){
ax[sC]=bob[bob[i]]; ay[sC]=bob[i];
sC++;
swap(&bob[bob[i]], &bob[i]);
}
}
return sC;
}
int findPos(int number){
for(int i=0;i<n;i++){
if(number==s[i]){
return i;
}
}
}
void insertSwaps(int t, int ss){
int i;
for(i=0;i<n;i++){
pos[s[i]]=i;
}
for(i=0;i<t;i++){
swap(&s[x[i]], &s[y[i]]);
swap(&pos[s[x[i]]], &pos[s[y[i]]]);
if(i<ss){
int a=pos[ax[i]], b=pos[ay[i]];
//printf("%d %d\n", a, b);
p[i]=a; q[i]=b;
swap(&s[a], &s[b]);
swap(&pos[s[a]], &pos[s[b]]);
}
else printf("0 0");
}
}
void solve(){
int l=0, r=n-1, sC, mid;
while(l<r){
mid=(l+r)/2;
doBob(mid);
sC=swapCount();
if(sC<=mid){
r=mid;
}
else l=mid+1;
}
ansR=r;
doBob(r);
sC=swapCount();
insertSwaps(r, sC);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n = N, s = S, x = X, y = Y, p = P, q = Q;
solve();
return ansR;
}