om1429888's blog

By om1429888, history, 22 months ago, In English
#include<iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fr(i,a,b) for(int i=a;i<b;i++)
#define loop(x,n) for(int x=0;x<n;x++)
#define mod 1e7
#define inf (1LL<<60)
#define all(x) (x).begin(),(x).end()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
void precal(){
}
ll helper(vector<ll>v1,vector<ll>v2,vector<pair<ll,ll>>&output){
 for(int i=0;i<v1.size();i++){
    int cur=i;
    for(int j=i+1;j<v1.size();j++){
        if(v1[j]<v1[cur])cur=j;
    }
    if(cur!=i){
      swap(v1[cur],v1[i]);
      swap(v2[cur],v2[i]);
      output.push_back({i,cur});
    }
  }
  for(int i=1;i<v1.size();i++){
      if(v2[i-1]>v2[i]){
        return -1;
      }
  }
  return  output.size();
}
void solve(){
  ll n;cin>>n;
  vector<ll>v1(n);
  vector<ll>v2(n);
  fr(i,0,n)cin>>v1[i];
  fr(i,0,n)cin>>v2[i];

  vector<pair<ll,ll>>output1;
  vector<pair<ll,ll>>output2;
  ll x=helper(v1,v2,output1);
  ll y=helper(v2,v1,output2);
  
  if(x==-1&&y==-1){
    cout<<-1<<endl;
    return;
  }
  if(x!=-1){
    cout<<x<<endl;
    for(int i=0;i<output1.size();i++){
      cout<<output1[i].first+1<<" "<<output1[i].second+1;
      cout<<endl;
    }
  }
  else{
     cout<<y<<endl;
    for(int i=0;i<output2.size();i++){
      cout<<output2[i].first+1<<" "<<output2[i].second+1;
     cout<<endl;
    }
  }
}
int main()
{
fast_io;
cout<<fixed;
cout<<setprecision(10);
precal();
int t=1;cin>>t;
for(int i=1;i<=t;i++)
{
//cout<<Case #<<i<<: ;
solve();
}
 return 0;
}
  • Vote: I like it
  • -24
  • Vote: I do not like it

»
22 months ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

After applying selection sort on v1, we are not sure that v2 is sorted as well. So we run selection sort once more on v2 with same operations on v1, if at the end both are sorted we output the answer else -1.Thus we need to call helper function only once.

ll helper(vector<ll>v1,vector<ll>v2,vector<pair<ll,ll>>&output){
 for(int i=0;i<v1.size();i++){
    int cur=i;
    for(int j=i+1;j<v1.size();j++){
        if(v1[j]<v1[cur])cur=j;
    }
    if(cur!=i){
      swap(v1[cur],v1[i]);
      swap(v2[cur],v2[i]);
      output.push_back({i,cur});
    }
  }

// run selection sort on v2 as well.

  for(int i=0;i<v1.size();i++){
    int cur=i;
    for(int j=i+1;j<v1.size();j++){
        if(v2[j]<v2[cur])cur=j;
    }
    if(cur!=i){
      swap(v1[cur],v1[i]);
      swap(v2[cur],v2[i]);
      output.push_back({i,cur});
    }
  }
// if any of them is still unsorted output -1
  for(int i=1;i<v1.size();i++){
      if(v2[i-1]>v2[i]){
        return -1;
      }
  }
  for(int i=1;i<v1.size();i++){
      if(v1[i-1]>v1[i]){
        return -1;
      }
  }
  return  output.size();
}