RKS - RK Sorting - SPOJ Solution C++

  Problem Link : RKS 


👉 Hint : Sorting with custom comparator

 


✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
bool comp(pair<ll,pair<ll,ll> >& p1,pair<ll,pair<ll,ll> >& p2)
{
	if(p1.second.first==p2.second.first)
		return p1.second.second<p2.second.second;
	else
		return p1.second.first>p2.second.first;	

}
int main()
{
	ll i,n;
	ll c;
	cin>>n>>c;
	ll arr[n];
	for(i=0;i<n;i++)
		cin>>arr[i];
	map<ll,pair<ll,ll> >m;
	for(i=0;i<n;i++)
	{
		m[arr[i]].first++;
		if(m[arr[i]].first==1)
			m[arr[i]].second=i;

	}	
	vector<pair<ll,pair<ll,ll> > >v;
	map<ll,pair<ll,ll> >:: iterator it;
	for(it=m.begin();it!=m.end();it++)
		v.push_back(make_pair(it->first,make_pair(it->second.first,it->second.second)));
	sort(v.begin(),v.end(),comp);
	vector<ll>van;
	van.reserve(n);
	for(i=0;i<v.size();i++)
	{
		ll x=v[i].second.first;
		while(x!=0)
		{
			van.push_back(v[i].first);
			x--;
		}
	}
	for(i=0;i<van.size();i++)
		cout<<van[i]<<" ";	
		


	return 0;
	
}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!