# PLANETS - Editorial

**URL:** <https://discuss.codechef.com/t/planets-editorial/105902>\
**Category:** editorial\
**Tags:** heap, set\
**Created:** [April 18, 2023, 4:02pm UTC](https://discuss.codechef.com/t/planets-editorial/105902 "2023-04-18T16:02:07Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![thebhavikjain](https://discuss.codechef.com/user_avatar/discuss.codechef.com/thebhavikjain/32/336723_2.png) [@thebhavikjain](https://discuss.codechef.com/u/thebhavikjain)\
**Post date:** [April 18, 2023, 4:02pm UTC](https://discuss.codechef.com/t/planets-editorial/105902/1 "2023-04-18T16:02:07Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/PLANETS)  
[Contest](https://www.codechef.com/CDUN2023/problems/PLANETS)

_ **Author:** _ [Bhavik Jain](https://www.codechef.com/users/thebhavikjain)  
_ **Tester:** _ [Dhrub Kumar](https://www.codechef.com/users/dhrub_kumar), [Gaurish Baliga](https://www.codechef.com/users/omniking)  
_ **Editorialist:** _ [Bhavik Jain](https://www.codechef.com/users/thebhavikjain)

# DIFFICULTY:

EASY-MEDIUM

# PREREQUISITES:

Set, Heap

# PROBLEM:

Planets of different sizes are born. There are three types of queries :

- Query 1 : **1 s** : Represents that a new planet of size _s_ is born
- Query 2 : **2** : Destroy the planet which is born first
- Query 3 : **3** : Destroy the planet with largest size. If there are multiple planets having largest size then among them, destroy the planet which is born first.

Planets are numbered according to the sequence 1, 2, 3,… in the order they are born.  
For each query of _type 2_ or _type 3_ , output an integer denoting the planet that has been destroyed in that particular query.  
It is ensured that there always exists at least one planet before a query of type 2 or 3.

# EXPLANATION:

Let’s create two sets, one to store the planet numbers and the second to store a pair consisting of ( planet size, -1 \* planet number ).  
The first set ensures that the planets are sorted in the order they are born.  
For the second set, it is ensured that the planets are sorted according to their sizes and in case of same sizes, the second term ( -1 \* planet number ) ensures that the order is sorted in the sequence they are born.  
We will also create a map for mapping the planet numbers to their respective sizes.

Now with all our data structures ready, we just have to process the queries.  
For query 1 : Add the planet number to set 1 and ( number, size) to set 2  
For query 2 : Remove the first element from set 1, output it and then using the map remove the respective pair from set 2 as well.  
For query 3 : Remove the last pair (largest size) from set 1, output the planet number and remove the planet number from set 1 as well.

This forms the solution for the problem.

# SOLUTIONS:

> **Setter's Solution (C++)**
>
> ```
> #include <bits/stdc++.h>
> using namespace std;
> 
> int main()
> {
> long t;
> cin>>t;
> while(t--)
> {
> long q;
> cin>>q;
> map<long,long> m;
> int cnt(0LL);
> set<long> s;
> set<pair<long,long>> p;
> vector<long> v;
> while(q--)
> {
> int n;
> cin>>n;
> if(n==1)
> {
> ++cnt;
> int x;
> cin>>x;
> m[cnt]=x;
> s.insert(cnt);
> p.insert(make_pair(x,-cnt));
> }
> else if(n==2) {
> int i = *s.begin();
> v.push_back(i);
> s.erase(i);
> p.erase(make_pair(m[i],-i));
> }
> else
> {
> int i = -p.rbegin()->second;
> s.erase(i);
> p.erase(make_pair(m[i],-i));
> v.push_back(i);
> }
> }
> for(auto i:v) {
> cout<<i<<' ';
> }
> cout<<'\n';
> }
> return 0;
> }
> 
> ```