1077D. Cutting Out - Codeforces Solution C++

➤  Problem Link : 1077D. Cutting Out 

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;

bool comp(int x,int y)
{
	return mp[x]>mp[y];
}

bool func(int cnt,vector<int> v, int k,bool flag)
{
	if(!flag)
	{
		int c=0;
		for(int i=0;i<v.size();i++)
		{
			c+=mp[v[i]]/cnt;
			if(c>=k)
				return 1;

			if(mp[v[i]]<cnt)
				return 0;
		}
		return 0;
	}
	else
	{
		for(int i=0;i<v.size();i++)
		{
			for(int j=1;j<=mp[v[i]]/cnt;j++)
			{
				k--;
				cout<<v[i]<<" ";
				if(k==0)
					return 1;
			}
		}
	}
	return 1;
}

int main()
{
	int n,k,v;
	cin>>n>>k;
	vector<int> s;
	for(int i=0;i<n;i++)
	{
		cin>>v;
		s.push_back(v);
	}
	mp.clear();
	for(auto i : s)
		mp[i]++;
	vector<int> t;
	for(auto it : mp)
		t.push_back(it.first);
	sort(t.begin(),t.end(),comp);

	int low = 0,high = 1000000,mid;

	while(low<high)
	{
		mid=low+(high-low+1)/2;
		if(func(mid,t,k,0))
			low=mid;
		else
			high=mid-1;
	}
	func(high,t,k,1);



}

 

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!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.