MSSORT - Editorial

PROBLEM LINK:

Practice

Contest

Author: Akash Choudhary

Tester: Chinmay Rakshit

Editorialist: Chinmay Rakshit

DIFFICULTY:

EASY, MEDIUM

PREREQUISITES:

FAST INPUT-OUTPUT ,BUILT-IN FUNCTION C++,STL CONTAINER

PROBLEM:

Input contains n integers sort the integers in decreasing order of their count of binary bit (1) in them and them again sort the integers having the same bit count into increasing order.

QUICK EXPLANATION:

The problem statement itself clear.

O(N^2) sorting will only pass the first subtask.
thus, you have to use quick sort or merge sort.Better will be to use sort function in algorithm.h

But still it is slow enough as to count the bits of each integer so we use inbuilt function
__builtin_popcount (b)

to count the bits set on.

But still it’s slow enough so now u have to use the fast input to pass the last subtask and thus, you will get full points.

The purpose of this question was to make the user understand the use of STL container and quickly create a strategy to overcome the TLE situation.

TESTER’S SOLUTIONS:

Tester’s solution can be found here.