| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 70133 | Vahan | 정렬하기 (IOI15_sorting) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "sorting.h"
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
vector<pair<int,int> > v;
int n,ps[300000],s[300000],x[300000],y[300000],rev_ps[300000],r[300000];
qayl_qan(int a[])
{
int q=n-1;
for(int i=0;i<n;i++)
{
if(a[i]==i)
q--;
else if(a[a[i]]==i && a[i]>i)
q--;
}
return q;
}
int stug(int e)
{
for(int i=0;i<n;i++)
ps[i]=s[i];
for(int i=0;i<=e;i++)
swap(ps[x[i]],ps[y[i]]);
if(qayl_qan(ps)<=e+1)
return 1;
else
return 0;
}
bin(int l,int r)
{
if(l==r)
return r;
int mid=(l+r)/2;
if(stug(mid))
bin(l,mid);
else
bin(mid+1,r);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
if(M>=N)
M=N-1;
for(int i=0;i<N;i++)
s[i]=S[i];
for(int i=0;i<M;i++)
{
x[i]=X[i];
y[i]=Y[i];
}
n=N;
if(qayl_qan(S)==0)
return 0;
int t=bin(0,M-1);
t++;
for(int i=0;i<n;i++)
ps[i]=s[i];
for(int i=0;i<t;i++)
swap(ps[x[i]],ps[y[i]]);
for(int i=0;i<n;i++)
rev_ps[ps[i]]=i;
for(int i=0;i<n;i++)
{
if(ps[rev_ps[i]]==ps[i])
continue;
int e=ps[i];
swap(ps[rev_ps[i]],ps[i]);
v.push_back({ps[i],e});
swap(rev_ps[i],rev_ps[e]);
}
for(int i=0;i<n;i++)
r[s[i]]=i;
for(int i=0;i<t;i++)
{
swap(s[x[i]],s[y[i]]);
swap(r[s[x[i]]],r[s[y[i]]]);
if(v.size()>i)
{
P[i]=r[v[i].first];
Q[i]=r[v[i].second];
}
else
{
P[i]=0;
Q[i]=0;
}
swap(s[P[i]],s[Q[i]]);
swap(r[s[P[i]]],r[s[Q[i]]]);
}
return t;
}