ShivanshuJaiswal15
BAN USER#include<bits/stdc++.h>
using namespace std;
int main()
{
/*Minimum number of swaps required to sort array algo with slight modification*/
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<pair<int,int> >v;
for(int i=0;i<n;i++)
{
int a;
cin>>a;
v.push_back(make_pair(a,i));
}
sort(v.begin(), v.end());
std::vector<int> vis(n,0);
int ans=0;
for(int i=0;i<n;i++)
{
if(vis[i] || v[i].second==i)
continue;
int cyc_size = 0;
int j=i;
while(!vis[j])
{
vis[j]=1;
cyc_size++;
j=v[j].second;
}
cyc_size++;
ans=ans+cyc_size;
}
cout<<ans<<endl;
// for(int i=0;i<n;i++)
// {
// cout<<v[i].first<<" "<<v[i].second<<endl;
// }
}
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long t;
cin>>t;
while(t--)
{
int hex[16];
memset(hex,0,sizeof(hex));
vector<int> arr(10000000,0);
long long n;
cin>>n;
while(n--)
{
long long x,y;
cin>>x>>y;
arr[x]=1;
arr[y]=-1;
}
//for(int i=1;i<=16;i++)
// cout<<arr[i]<<" ";
//cout<<endl;
int j=0;
int ans[4];
int count=0;
for(int i=1;i<=10000000;i++)
{
if(arr[i]==1 && count%2==0)
{
//cout<<"1 "<<i<<endl;
ans[j]=1;
j++;
count++;
}
else if(arr[i]==1 && count%2==1)
{
//cout<<"2 "<<i<<endl;
ans[j]=0;
j++;
count++;
}
if(arr[i]==-1 && count%2==0)
{
//cout<<"3 "<<i<<endl;
ans[j]=0;
j++;
count--;
}
else if(arr[i]==-1 && count%2==1)
{
//cout<<"4 "<<i<<endl;
ans[j]=1;
j++;
count--;
}
if(arr[i]==0 && count%2==0)
{
//cout<<"5 "<<i<<endl;
ans[j]=0;
j++;
}
else if(arr[i]==0 && count%2==1)
{
//cout<<"6 "<<i<<endl;
ans[j]=1;
j++;
}
if(j==4)
{
j=0;
//cout<<ans[0]<<ans[1]<<ans[2]<<ans[3]<<endl;
int num=8*ans[0]+4*ans[1]+2*ans[2]+ans[3];
ans[0]=ans[1]=ans[2]=ans[3]=0;
hex[num]++;
}
}
for(int i=0;i<16;i++)
cout<<hex[i]<<" ";
cout<<endl;
}
}
- ShivanshuJaiswal15 July 10, 2017