# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
318154 | tigicha | Sorting (IOI15_sorting) | C++14 | 386 ms | 21460 KiB |
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 <bits/stdc++.h>
#include "sorting.h"
using namespace std;
int l, r, ans, m, b[500005], a[500005];
vector<pair<int, int> > v;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
l=0;
r=M;
ans=-1;
while(l<=r){
m=(l+r)/2;
for(int i=0; i<N; i++)
b[i]=S[i];
for(int i=0; i<m; i++)
swap(b[X[i]], b[Y[i]]);
for(int i=0; i<N; i++)
a[b[i]]=i;
v.clear();
for(int i=0; i<N; i++){
if(b[i]==i) continue;
v.push_back(make_pair(i, b[i]));
swap(b[i], b[a[i]]);
swap(a[i], a[b[a[i]]]);
}
if(v.size()>m) l=m+1;
else{
for(int i=0; i<N; i++){
b[i]=S[i];
a[b[i]]=i;
}
for(int i=0; i<M; i++){
swap(a[b[X[i]]], a[b[Y[i]]]);
swap(b[X[i]], b[Y[i]]);
if(i<v.size()){
P[i]=a[v[i].first];
Q[i]=a[v[i].second];
swap(a[v[i].first], a[v[i].second]);
swap(b[a[v[i].first]], b[a[v[i].second]]);
}
else{
P[i]=0;
Q[i]=0;
}
}
r=m-1;
ans=m;
}
}
return ans;
}
Compilation message (stderr)
# | 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... |