962D. Merge Equals - Codeforces Solution C++

➤  Problem Link : 962D. Merge Equals 

✅ C++ Solution :

 
#include<bits/stdc++.h>
using namespace std;

#define ll long long int

unordered_map<ll,ll> us;

bool comp(ll x, ll y)
{
	return us[x]<us[y];
}

int main()
{
	ll x;
	int n;
	cin>>n;
	map<ll,set<int> > mp;
	vector<ll> vec;
	for(int i=0;i<n;i++)
	{
		cin>>x;
		mp[x].insert(i);
	}
	ll v;
	set<int> s;
	for(auto it = mp.begin();it!=mp.end();it++)
	{
		v= it->first;
		s=it->second;
		auto i=s.begin();
		while(i!=s.end())
		{
			i++;
			if(i==s.end())		// odd
			{
				i--;
				us[v]=*i;
				vec.push_back(v);
				break;
			}
			mp[2*v].insert(*i);
			i++;
		}

	}

	sort(vec.begin(),vec.end(),comp);
	cout<<vec.size()<<"\n";
	for(ll v : vec)
		cout<<v<<" ";
}

 

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.