Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

    • Speed up the ranking algorithm

    At an old tournament, the software engineers implemented a ranking algorithm based on bubble sort. Back then the tournament didn’t have many participants - so that worked okay. But now the number of participants is too many. They ask you to speed up the ranking algorithm.
    Each team has a unique number (an identifier) and a score. The teams have to be ordered in descending order of scores (highest scores first, lowest scores last), and the teams with the same scores should stay relevant to the order they appear in the input. So, you should implement a stable sort.

    Input

    The first line of the input contains a single integer n (1 ≤ n ≤ ).
    The next n lines contain space-separated pairs () representing the unique identifier of a team and the score the team earned.

    Output

    The program should print n lines. Each line should contain two integers - the id of the team, and their score.

    Examples

    Input
    Output
    6 1 10 4 20 5 7 2 20 8 10 9 15
    4 20 2 20 9 15 1 10 8 10 5 7
     

    Constraints

    Time limit: 2.5 seconds

    Memory limit: 512 MB

    Output limit: 10 MB

    To check your solution you need to sign in
    Sign in to continue