PLANETS - Editorial

PROBLEM LINK:

Practice
Contest

Author: Bhavik Jain
Tester: Dhrub Kumar, Gaurish Baliga
Editorialist: Bhavik Jain

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;
}