CHEFHIRE - Editorial

editorial
, , ,
1

Problem Link:

Contest

Practice

Author: Abhishek Pratap Singh

Tester: Sufiyan Ansari, Snigdh

Editorialist: Abhishek Pratap Singh

Difficulty

EASY

PREREQUISITES

Sorting Algorithms

PROBLEM

To hire some new talents in his company, Chef recently visited one of the top Universities of Chefland, where he got the list of student details(name, Academic Score, Other Score).
‎‎‎‎‎‎
Since Chef is interested in hiring the best talents he wants the list of students arranged in non-increasing order according to their academic scores, but he also wants to maintain original relative ordering if two or more students have the same academic score.

Can you help Chef to hire the best talents by rearranging the list of students in the required format?

EXPLANATION & SOLUTION:

Stable sorting algorithm maintains the relative order of records with equal keys (i.e. values).
That is, a sorting algorithm is stable if whenever there are two records R and S with the same
key and with R appearing before S in the original list, R will appear before S in the sorted list.

From the above definition, it is clear that we are asked to perform stable sort

Solution:

Setter's Solution 
/*
Author : Abhishek Pratap Singh
Codechef: av1shek
Codeforces: av1shek
*/

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll      long long


struct node{
    string name;
    ll score;
    ll other;
};

bool comp(node a, node b){
    return a.score > b.score;
}

void testcase()
{
    ll n; cin>>n;
    node students[n];

    for(ll i=0; i<n; i++)
        cin>>students[i].name>>students[i].score>>students[i].other;

    stable_sort(students, students+n, comp);

    for(ll i=0; i<n; i++)
        cout<<students[i].name<<" "<<students[i].score<<" "<<students[i].other<<endl;

}
int main()
{
    fast;

    ll tc=1;
    cin>>tc;

    for(ll i=1;i<=tc;i++)
        testcase();
    return 0;
}
Tester's Solution 
/*
Author : Mohd Sufiyan Ansari
g++ -std=c++17  -o sufi
Love it and You will be loved.
*/

#include<bits/stdc++.h>

#define test_cases true
#define ll long long int
#define ull unsigned long long int
#define vll vector<ll>
#define vvll vector<vll>
#define pll pair<ll,ll>
#define vpl vector<pll>
#define matrix(x,n,m) vector<vll>x(n,vll(m))
#define mll map<ll,ll>
#define itr iterator
#define MIT(T,X) map<T,X>::iterator
#define loop(i,x,n) for(int i=x;i<n;i++)
#define PB push_back
#define pB pop_back
#define MP make_pair
#define ff first
#define ss second
#define all(x) (x).begin(),(x).end()
#define PI 3.141592653589793238462
#define test int t=1;if(test_cases)cin>>t;for(int T=1;T<=t;T++)
#define FIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define desc(x) sort(all(x)),reverse(all(x))
#define mod 1000000007
#define mod1 998244353
#define INF 1e18
#define sz(p) p.size()
#define endl "\n"
#define yes cout<<"YES\n"
#define no cout<<"NO\n";
#define Case(n) cout<<"Case #"<<n<<": "
#define ANS cout<<ans<<"\n"

using namespace std;

template <typename T> void print(T &p){cout<<p<<" ";}
template <typename T> void print(T v[],int n){for(int i=0;i<n;i++)print(v[i]);}
template <typename T> void print(pair<T,T> p){cout<<p.ff<<" "<<p.ss<<"\n";}
template <typename T> void print(vector<T> &v){int size=v.size();for(int i=0; i<size; i++) print(v[i]);cout<<endl;}
template <typename T> void print(vector<vector<T>> &v){for(auto i : v)print(i);}
template <typename T> void print(map<T,ll> &ma){for(auto it:ma)cout<<it.ff<<" "<<it.ss<<"\n";}
template <typename T> void read(T &n){cin>>n;}
template <typename T> void read(vector<T> &v){for(int i=0;i<v.size();i++)read(v[i]);}
template <typename T> void read(T v[],int n){for(int i=0;i<n;i++)cin>>v[i];}

/* ----------- MAIN PROGRAM ------------- */

bool comp(pair<pair<int,string>,pair<int,string>> &a, pair<pair<int,string>,pair<int,string>> &b)
{
    if(a.second.first != b.second.first)
        return a.second.first > b.second.first;
    else{
        return a.first.first < b.first.first;
    }
}

void sufiyan(int T)
{
    int n;
    cin>>n;
    vector<pair<pair<int,string>,pair<int,string>>>v(n);
    for(int i=0;i<n;i++)
    {
        cin>>v[i].first.second>>v[i].second.first>>v[i].second.second;
        v[i].first.first = i;
    }
    sort(all(v),comp);
    for(auto i:v)
        cout<<i.first.second<<" "<<i.second.first<<" "<<i.second.second<<"\n";
}

/* --------------- DRIVER PROGRAM -------------------- */

int main()
{
    FIO;
    test sufiyan(T);
    return 0;
}

Please comment below if you have any doubts and Feel free to share any alternative solution(s).

1 Like