# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
587520 | benson1029 | Sorting (IOI15_sorting) | C++14 | 3 ms | 468 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 "sorting.h"
#include<bits/stdc++.h>
using namespace std;
int a[200005], b[200005], s[200005];
bool stexists[200005];
vector< pair<int,int> > v;
queue<int> st;
void swapa(int x, int y) {
b[a[x]] = y;
b[a[y]] = x;
if(!stexists[x] && stexists[y]) {
st.push(x);
}
else if(stexists[x] && !stexists[y]) {
st.push(y);
}
swap(stexists[x], stexists[y]);
swap(a[x], a[y]);
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
int l = 0, r = N, mid;
while(l <= r) {
mid = (l+r)/2;
for(int i=0; i<N; i++) {
a[i] = i;
s[i] = S[i];
}
for(int i=mid-1; i>=0; i--) {
swap(a[X[i]], a[Y[i]]);
}
while(!st.empty()) st.pop();
for(int i=0; i<N; i++) {
stexists[i] = (a[i] != s[i]);
if(a[i] != s[i]) st.push(i);
b[a[i]] = i;
}
v.clear();
for(int i=0; i<mid; i++) {
swapa(X[i], Y[i]);
swap(s[X[i]], s[Y[i]]);
int j = 200001;
while(!st.empty() && !stexists[j]) {
j = st.front(); st.pop();
}
if(!stexists[j]) {
v.push_back({0, 0});
continue;
}
int k = b[s[j]];
swap(s[j], s[k]);
v.push_back({j, k});
if(s[j] == a[j]) {
stexists[j] = false;
}
if(s[k] == a[k]) {
stexists[k] = false;
}
}
if(l==r) {
for(int i=0; i<v.size(); i++) P[i] = v[i].first, Q[i] = v[i].second;
return v.size();
} else {
while(!st.empty() && !stexists[st.front()]) st.pop();
if(st.empty()) r = mid;
else l = mid+1;
}
}
}
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... |