Блог пользователя om1429888

Автор om1429888, история, 2 года назад, По-английски
#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;
}
  • Проголосовать: нравится
  • -24
  • Проголосовать: не нравится

»
2 года назад, # |
Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

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();
}