This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]){
int l = 0,r = M;
while(l < r){
int m = (l + r)/2;
vector<int> v;
vector<int> pos2(N,0);
for(int i = 0;i<N;i++){
v.push_back(S[i]);
pos2[S[i]] = i;
}
vector<int> ord(N,0);
iota(ord.begin(),ord.end(),0);
vector<int> pos = ord;
for(int i = m-1;i>=0;i--){
pos[ord[Y[i]]] = X[i];
pos[ord[X[i]]] = Y[i];
swap(ord[X[i]],ord[Y[i]]);
}
int last = -1;
for(int i = 0;i<m;i++){
pos[ord[Y[i]]] = X[i];
pos[ord[X[i]]] = Y[i];
swap(ord[X[i]],ord[Y[i]]);
pos2[v[Y[i]]] = X[i];
pos2[v[X[i]]] = Y[i];
swap(v[X[i]],v[Y[i]]);
last++;
while(last < N && pos2[last] == pos[last]){
last++;
}
if(last < N){
pos2[v[pos[last]]] = pos2[last];
swap(v[pos2[last]],v[pos[last]]);
pos2[last] = pos[last];
}
}
if(is_sorted(v.begin(),v.end())){
r = m;
}
else l = m + 1;
}
int m = l;
vector<int> v;
vector<int> pos2(N,0);
for(int i = 0;i<N;i++){
v.push_back(S[i]);
pos2[S[i]] = i;
}
vector<int> ord(N,0);
iota(ord.begin(),ord.end(),0);
vector<int> pos = ord;
for(int i = m-1;i>=0;i--){
pos[ord[Y[i]]] = X[i];
pos[ord[X[i]]] = Y[i];
swap(ord[X[i]],ord[Y[i]]);
}
int last = -1;
for(int i = 0;i<m;i++){
pos[ord[Y[i]]] = X[i];
pos[ord[X[i]]] = Y[i];
swap(ord[X[i]],ord[Y[i]]);
pos2[v[Y[i]]] = X[i];
pos2[v[X[i]]] = Y[i];
swap(v[X[i]],v[Y[i]]);
last++;
P[i] = Q[i] = 0;
while(last < N && pos2[last] == pos[last]){
last++;
}
// for(auto u:v){
// cout << u << ' ';
// }
// cout << endl;
// cout << last << endl;
// cout << pos[last] << ' ' << pos2[last] << endl;
if(last < N){
P[i] = pos2[last];
Q[i] = pos[last];
pos2[v[pos[last]]] = pos2[last];
swap(v[pos2[last]],v[pos[last]]);
pos2[last] = pos[last];
}
// for(auto u:v){
// cout << u << ' ';
// }
// cout << endl;
}
assert(is_sorted(v.begin(),v.end()));
return m;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |