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;
typedef vector<int> vi;
int n;
vector <int> s,x,y,p,q;
int ans = 0;
void merge(int l, int r, int mid){
vi a;
vi b;
for(int i = l; i<=mid; i++) a.push_back(s[i]);
for(int i = mid+1; i<=r; i++) b.push_back(s[i]);
int i = 0, j = 0, k = l;
while(i<=mid-l and j<=r-(mid+1)){
if(a[i]>b[j]){
swap(s[x[ans]],s[y[ans]]);
p[ans] = k; q[ans] = j+mid+1;
ans++;
s[k] = b[j]; j++; k++;
}
else{
swap(s[x[ans]],s[y[ans]]);
p[ans] = k; q[ans] = i+l;
ans++;
s[k] = a[i]; i++; k++;
}
}
while(i<=mid-l){
swap(s[x[ans]],s[y[ans]]);
p[ans] = k; q[ans] = i+l;
ans++;
s[k] = a[i]; i++; k++;
}
while(j<=r-(mid+1)){
swap(s[x[ans]],s[y[ans]]);
p[ans] = k; q[ans] = j+mid+1;
ans++;
s[k] = b[j]; j++; k++;
}
}
void separate(int l, int r){
if(l<r){
int mid = (l+r)>>1;
separate(l,mid);
separate(mid+1,r);
merge(l,r,mid);
}
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
if(N == 1){
P[0] = 0;
Q[0] = 0;
return 1;
}
n = N;
for(int i = 0; i<n; i++) s.push_back(S[i]);
for(int i = 0; i<M; i++) x.push_back(X[i]), y.push_back(Y[i]);
p.assign(M,0);
q.assign(M,0);
int ind1 = 0, ind2 = 0; int mn = INT_MAX;
for(int i = 0; i<N; i++){
if(s[i]<mn){
mn = s[i];
ind1 = i;
}
}
if(ind1 > 0){
swap(s[x[ans]],y[ans]);
p[ans] = 0; q[ans] = ind1;
swap(s[0],s[ind1]); ans++;
}
int indx = -1;
if(x[ans] == 0 || y[ans] == 0 and x[ans]!=y[ans]){
indx = 0;
}
else indx = 1;
mn = INT_MAX;
for(int i = 0; i<n; i++){
if(i == (indx^1)) continue;
if(s[i]<mn){
mn = s[i]; ind2 = i;
}
}
if(ind2>1){
swap(s[x[ans]],s[y[ans]]);
swap(s[indx],s[ind2]); ans++;
}
separate(2,n-1);
if(s[0]>s[1]){
swap(s[x[ans]],s[y[ans]]);
if(s[0]>s[1]){
p[ans] = 0; q[ans] = 1; ans++;
}
else p[ans] = 0, q[ans] = 0, ans++;
}
for(int i = 0; i<M; i++) P[i] = p[i], Q[i] = q[i];
return ans;
}
Compilation message (stderr)
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:86:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
86 | if(x[ans] == 0 || y[ans] == 0 and x[ans]!=y[ans]){
# | 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... |