| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 519032 | ymm | 정렬하기 (IOI15_sorting) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
///
/// Oh? You're approaching me?
///
#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;
#include "sorting.h"
const int N = 2e5+10;
int a[N], b[N];
int *S, *X, *Y, *P, *Q;
int n, m;
void init(int* s){
Loop(i,0,n) a[i] = s[i], b[s[i]] = i;
}
void swp(int i, int j){
swap(b[a[i]], b[a[j]]);
swap(a[i], a[j]);
}
bool can(int k){
init(S);
Loop(i,0,k)
swp(X[i], Y[i]);
int cnt=0;
static bitset<N> vis;
vis.reset();
Loop(i,0,n){
if(vis[i]) continue;
++cnt;
int j=i;
while(!vis[j])
vis[j]=1, j=a[j];
}
return n-cnt<=k;
}
void solve(int k){
init(S);
Loop(i,0,k)
swp(X[i], Y[i]);
int j=0;
for(int i=0; i<n; ++i){
if(b[i] != i){
P[j] = a[i];
Q[j] = a[b[i]];
swp(i, b[i]);
++j;
}
}
assert(j==k)
init(S);
Loop(i,0,k){
swp(X[i], Y[i]);
P[i] = b[Q[i]];
Q[i] = b[P[i]];
}
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n=N; m=M; ::S=S; ::X=X; ::Y=Y; ::P=P; ::Q=Q;
int l=0, r=m;
while(l<r){
int m=(l+r)/2;
if(can(m)) r=m;
else l=m+1;
}
solve(l);
return l;
}