| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 921978 | 2024-02-04T15:41:53 Z | coding_snorlax | 정렬하기 (IOI15_sorting) | C++14 | 0 ms | 0 KB |
#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
int Answer[10000],vis[10000],Goal[10000],inv_S[10000];
int n;
set<int> OK;
int Count_cycle(int S[]){
for(int i=0;i<n;i++){
vis[i]=0;
}
for(int i=0;i<n;i++){
Goal[S[i]]=Answer[i];
}
int answer = n;
for(int i=0;i<n;i++){
if(!vis[i]){
vis[i]=1;
int st = i,now = i;
while(Goal[now]!=st){
now = Goal[now];
vis[now]=1;
}
answer-=1;
}
}
return answer;
}
void find_Sol(int P[],int Q[],int S[],int ope){
for(int i=0;i<n;i++){
if(S[i]!=Answer[i]){
int j = inv_S[Answer[i]];
inv_S[S[j]]=i;
inv_S[S[i]]=j;
P[ope]=i;
Q[ope]=j;
S[j]=S[i];
S[i]=Answer[i];
return;
}
}
P[ope]=0;Q[ope]=0;
}
int Check(int k,int S[],int X[],int Y[]){
for(int i=0;i<n;i++){
Answer[i]=i;
}
for(int i=k-1;i>=0;i--){
int tmp = Answer[X[i]];
Answer[X[i]]=Answer[Y[i]];
Answer[Y[i]]=tmp;
}
if(Count_cycle(S)<=k) return 1;
else return 0;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n=N;
int L = 0,R = N;
while(L!=R){
int m = (L+R)/2;
if(Check(m,S,X,Y)) R=m;
else L=m+1;
}
Check(L,S,X,Y);
for(int i=0;i<N;i++){
inv_S[S[i]]=i;
}
for(int i=0;i<L;i++){
int tmp = S[X[i]];
inv_S[S[X[i]]]=Y[i];
inv_S[S[Y[i]]]=X[i];
S[X[i]]=S[Y[i]];
S[Y[i]]=tmp;
tmp = Answer[X[i]];
Answer[X[i]]=Answer[Y[i]];
Answer[Y[i]]=tmp;
debug();
find_Sol(P,Q,S,i);
}
return L;
}