Problem Link : - [http://www.codechef.com/CODE2015/problems/RIT04]
Author :- [http://www.codechef.com/users/dvlpr_expert]
Tester :- [http://www.codechef.com/users/dvlpr_expert]
Editorialist :- [http://www.codechef.com/users/dvlpr_expert]
DIFFICULTY :- Easy
PREREQUISITES :- Maths
PROBLEM :-
Poornima is celebrating its annual Techno-Cultural Fest AAROHAN. The IT student Kriti has agreed to supply candies for this festive season. Kriti has prepared N boxes of candies, numbered 1 to N (Each number occurring exactly once ). Kriti is very particular about the arrangement of boxes. She wants boxes to be arranged in a particular order, but unfortunately Kriti is busy. She has asked you to rearrange the boxes for her. Given the current order of boxes, you have to rearrange the boxes in the specified order. However there is a restriction. You can only swap two adjacent boxes to achieve the required order. Output, the minimum number of such adjacent swaps required.
EXPLANATION :-
You need to swap the numbers until you get the required sequence and the number swapping should be minimum.
SOLUTION :-
#include<iostream>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<cstdio>
using namespace std;
long long int a;
int arr[1000001];
void mergeSort(int s,int mid,int e)
{
int temp[e-s+1];
int k=0;
int i,j;
i=s;
j=mid+1;
while(i<=mid&&j<=e)
{
if(arr[j]<=arr[i])
{
temp[k++]=arr[j];
a+=(mid-i+1);
j++;
}
else
{
temp[k++]=arr[i];
i++;
}
}
while(i<=mid)
{
temp[k++]=arr[i];
i++;
}
while(j<=e)
{
temp[k++]=arr[j];
j++;
};
int p=0;
for(int i=s;i<=e;i++)
arr[i]=temp[p++];
}
void Sort(int s,int e)
{
if(s<e)
{
int a,b,c;
int mid=(s+e)/2;
Sort(s,mid);
Sort(mid+1,e);
mergeSort(s,mid,e);
}
}
int main()
{
int t,N;
scanf("%d",&t);
int num;
while(t--)
{
scanf("%d",&N);
int A[N+1];
for(int i=0;i<N;i++)
{
scanf("%d",&num);
A[num]=i;
}
for(int i=0;i<N;i++)
{
scanf("%d",&num);
arr[i]=A[num];
}
a=0;
Sort(0,N-1);
cout<<a<<endl;
}
}