| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 669777 | alvingogo | 정렬하기 (IOI15_sorting) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
int n;
void print(vector<int> s){
for(int i=0;i<n;i++){
cout << s[i] << " ";
}
cout << "\n";
}
void print2(int s[]){
for(int i=0;i<n;i++){
cout << s[i] << " ";
}
cout << "\n";
}
int findSwapPairs(int N,int S[],int M,int X[],int Y[],int P[],int Q[]){
int l=0,r=M;
n=N;
while(r>l){
int m=(l+r)/2;
vector<int> v(n);
iota(v.begin(),v.end(),0);
for(int i=0;i<m;i++){
swap(v[X[i]],v[Y[i]]);
}
vector<int> g(n);
for(int i=0;i<n;i++){
g[v[i]]=i;
}
v=g;
for(int i=0;i<n;i++){
g[v[i]]=S[i];
}
vector<int> vis(n);
int cnt=0;
for(int i=0;i<n;i++){
if(!vis[i]){
cnt++;
vis[i]=1;
int a=i;
while(1){
a=g[a];
if(vis[a]){
break;
}
vis[a]=1;
}
}
}
int t=n-cnt;
if(t<=m){
r=m;
}
else{
l=m+1;
}
}
vector<int> v(n);
iota(v.begin(),v.end(),0);
for(int i=0;i<l;i++){
swap(v[X[i]],v[Y[i]]);
}
vector<int> g(n);
for(int i=0;i<n;i++){
g[v[i]]=i;
}
v=g;
vector<int> d(n),e(n);
for(int i=0;i<n;i++){
d[S[i]]=i;
e[v[i]]=i;
}
vector<int> vis(n);
int c=0,cn=0;
set<int> u;
for(int i=0;i<n;i++){
if(v[i]!=S[i]){
u.insert(i);
}
}
for(int i=0;i<l;i++){
{
int t=X[i],f=Y[i];
swap(d[S[t]],d[S[f]]);
swap(S[t],S[f]);
swap(e[v[t]],e[v[f]]);
swap(v[t],v[f]);
if(v[t]!=S[t]){
u.insert(t);
}
else{
u.erase(t);
}
if(v[f]!=S[f]){
u.insert(f);
}
else{
u.erase(f);
}
}
if(!u.size()){
continue;
}
auto cn=*u.begin();
u.erase(cn);
assert(v[cn]!=S[cn]);
if(v[cn]!=S[cn]){
int t=cn,f=d[v[cn]];
swap(d[S[t]],d[S[f]]);
swap(S[t],S[f]);
if(v[t]!=S[t]){
u.insert(t);
}
else{
u.erase(t);
}
if(v[f]!=S[f]){
u.insert(f);
}
else{
u.erase(f);
}
P[c]=t;
Q[c]=f;
c++;
}
}
if(c<l){
P[c]=Q[c]=0;
c++;
}
return l;
}
int main(){
int N, M;
cin >> N;
int *S = (int*)malloc(sizeof(int) * (unsigned int)N);
for (int i = 0; i < N; ++i)
cin >> S[i];
cin >> M;
int *X = (int*)malloc(sizeof(int) * (unsigned int)M), *Y = (int*)malloc(sizeof(int) * (unsigned int)M);
for (int i = 0; i < M; ++i) {
cin >> X[i];
cin >> Y[i];
}
int *P = (int*)malloc(sizeof(int) * (unsigned int)M), *Q = (int*)malloc(sizeof(int) * (unsigned int)M);
int ans = findSwapPairs(N, S, M, X, Y, P, Q);
cout << ans << "\n";
for (int i = 0; i < ans; ++i)
cout << P[i] << " " << Q[i] << "\n";
return 0;
}