| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 793886 | Jarif_Rahman | 도시들 (IOI15_towns) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "sorting.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
vector<pair<int, int>> get_swaps(vector<int> S){
int n = S.size();
vector<pair<int, int>> swaps;
vector<int> pos(n);
for(int i = 0; i < n; i++) pos[S[i]] = i;
vector<bool> bl(n, 0);
for(int i = 0; i < n; i++){
if(bl[S[i]]) continue;
if(S[i] == i){
bl[i] = 1;
continue;
}
int j = i;
while(1){
if(bl[S[j]]){
bl[j] = 1;
break;
}
swaps.pb({S[j], j});
bl[j] = 1;
j = S[j];
}
}
return swaps;
}
int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]){
bool sorted = 1;
for(int i = 0; i < n; i++) sorted&=(S[i] == i);
if(sorted) return 0;
int k;
vector<int> s(n);
for(int i = 0; i < n; i++) s[i] = S[i];
int a = 0, b = m-1;
int ls = -1;
while(a < b){
int md = (a+b)/2;
while(ls < md){
ls++;
swap(s[X[ls]], s[Y[ls]]);
}
while(ls > md){
swap(s[X[ls]], s[Y[ls]]);
ls--;
}
if(get_swaps(s).size() <= md+1) b = md;
else a = md+1;
}
k = a;
vector<int> pos(n);
for(int i = 0; i < n; i++) pos[S[i]] = i;
auto swaps = get_swaps(s);
for(int i = 0; i <= k; i++){
swap(S[X[i]], S[Y[i]]);
swap(pos[S[X[i]]], pos[S[Y[i]]]);
if(i >= swaps.size()) P[i] = 0, Q[i] = 0;
else{
auto [x, y] = swaps[i];
swap(pos[x], pos[y]);
swap(S[pos[x]], S[pos[y]]);
P[i] = pos[x], Q[i] = pos[y];
}
}
return k+1;
}