# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1102973 | Pioneer | Sorting (IOI15_sorting) | C++17 | 25 ms | 592 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;
const int MAX=200000;
int n,m;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
n=N,m=M;
vector<int> v(n),need(n);
vector<pair<int,int>> swaps;
for(int i=0;i<n;i++)v[i]=S[i],need[i]=i;
for(int i=0;i<m;i++){
swap(v[X[i]],v[Y[i]]);
vector<int> tov=need;
for(int j=i+1;j<m;j++){
swap(tov[X[j]],tov[Y[j]]);
}
// cout<<"! "<<X[i]<<" "<<Y[i]<<"\n";
// for(int j=0;j<n;j++)cout<<tov[j]<<" ";
// cout<<"\n";
// for(int j=0;j<n;j++)cout<<v[j]<<" ";
// cout<<"\n";
// cout<<"\n";
vector<int> tov1(n);
for(int i=0;i<n;i++)tov1[tov[i]]=i;
swap(tov,tov1);
bool ok=0;
for(int k=0;k<n;k++){
if(tov[k]!=v[k]){
for(int j=0;j<n;j++){
if(tov[j]==v[k]){
ok=1;
swaps.push_back({k,j});
swap(v[k],v[j]);
break;
}
}
if(ok)break;
}
if(ok)break;
}
// tov=need;
// for(int j=i+1;j<m;j++){
// swap(tov[X[j]],tov[Y[j]]);
// }
// for(int j=0;j<n;j++)cout<<tov[j]<<" ";
// cout<<"\n";
// for(int j=0;j<n;j++)cout<<v[j]<<" ";
// cout<<"\n";
// cout<<"\n";
if(!ok)swaps.push_back({0,0});
}
// for(int i=1)
// for(int x:v)cout<<x<<" ";
// cout<<"\n";
assert(v==need);
for(int i=0;i<m;i++){
P[i]=swaps[i].first;
Q[i]=swaps[i].second;
}
return M;
}
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... |