// Arup Guha
// 10/9/2025
// Solution to COP 3502 Program 4A: Rank List via Merge Sort

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXSIZE 12
#define NUMGAMES 7
#define TOTAL 6
#define BASECASESIZE 30

const char GAMES[NUMGAMES][MAXSIZE+1] = {"Wordle", "Spelling Bee", "Crossword", "Connections", "Strands", "Letter Boxed", "Total"};

typedef struct Player {
    char* name;
    int scores[NUMGAMES];
} Player;

void initPlayer(Player* ptr, char* pName);
void update(Player* ptr, int key, int score);
int compare(Player* ptrP1, Player* ptrP2, int key);
void mergeSort(Player** list, int n, int key);
void mergeSortRec(Player** list, int low, int high, int key);
void merge(Player** list, int low, int mid, int high, int key);
void selectionSort(Player** list, int low, int high, int key);
void swap(Player** list, int i, int j);
void printPlayer(Player* ptr, int rank, int key);

int main() {

    int n;
    scanf("%d", &n);

    // Allocate the array of pointers.
    Player** playerList = calloc(n, sizeof(Player*));

    // Read in player info.
    for (int i=0; i<n; i++) {

        // Read in name and allocate one player.
        playerList[i] = malloc(sizeof(Player));
        char tempName[MAXSIZE+1];
        scanf("%s", tempName);
        initPlayer(playerList[i], tempName);

        // Read in their scores and update.
        for (int j=0; j<NUMGAMES-1; j++) {
            int add;
            scanf("%d", &add);
            update(playerList[i], j, add);
        }
    }

    // Read in sorting key.
    int sortBy;
    scanf("%d", &sortBy);

    // Sort it!
    mergeSort(playerList, n, sortBy);

    // Print the rank list.
    printf("%s Ranklist\n", GAMES[sortBy]);
    for (int i=0; i<n; i++)
        printPlayer(playerList[i], i+1, sortBy);

    // Free the memory.
    for (int i=0; i<n; i++)
        free(playerList[i]);
    free(playerList);

    return 0;

}

// Initializes the player pointed to by ptr to have the name pointed to by pName.
void initPlayer(Player* ptr, char* pName) {

    // Set the name.
    int len = strlen(pName);
    ptr->name = calloc(len+1, sizeof(char));
    strcpy(ptr->name, pName);

    // Set all scores to 0.
    for (int i=0; i<NUMGAMES; i++)
        ptr->scores[i] = 0;
}

// Updates the player pointed to by ptr's score in the game indicate by key to score
// and updates their total score as well.
void update(Player* ptr, int key, int score) {
    ptr->scores[key] += score;
    ptr->scores[TOTAL] += score;
}

// Returns a negative integer if the player pointed to by ptrP1 comes before the player
// pointed to by ptrP2 on the ranklist according to the game key, breaking ties by
// player name in alphabetical order.
int compare(Player* ptrP1, Player* ptrP2, int key) {

    // Take care of all cases where scores are different.
    if (ptrP1->scores[key] != ptrP2->scores[key])
        return ptrP2->scores[key] - ptrP1->scores[key];

    // Break ties by name.
    return strcmp(ptrP1->name, ptrP2->name);
}

// Merge Sorts the array list of size n according to the game indicated by key.
void mergeSort(Player** list, int n, int key) {
    mergeSortRec(list, 0, n-1, key);
}

// Recursively Merge Sorts list[low..high] base don key.
void mergeSortRec(Player** list, int low, int high, int key) {

    // Required by the assignment - take care of smaller arrays via O(n^2) sort.
    if (high - low < BASECASESIZE) {
        selectionSort(list, low, high, key);
        return;
    }

    // Usual Merge Sort Breakdown.
    int mid = (low+high)/2;
    mergeSortRec(list, low, mid, key);
    mergeSortRec(list, mid+1, high, key);
    merge(list, low, mid, high, key);
}

// Runs a merge on list[low..mid] and list[mid+1..high] according to key.
// Assumes both sublists are already sorted according to key.
void merge(Player** list, int low, int mid, int high, int key) {

    // Store copied sorted list here.
    Player** tmp = calloc(high-low+1, sizeof(Player*));

    // i is index to left list, j to right list, k to copied list.
    int i = low, j = mid+1, k = 0;

    // Go till we've copied everything.
    while (i<=mid || j<=high) {

        // Comes from first list.
        if (j>high || (i<=mid && compare(list[i],list[j], key) < 0))
            tmp[k++] = list[i++];

        // Comes from second list.
        else
            tmp[k++] = list[j++];
    }

    // Copy back.
    for (i=low; i<=high; i++)
        list[i] = tmp[i-low];
}

// Prints the player pointed to by ptr with rank rank and their score in game key.
void printPlayer(Player* ptr, int rank, int key) {
    printf("%d. %-15s %d\n", rank, ptr->name, ptr->scores[key]);
}

// Performs a Selection Sort in the subarray list[low..high] based on the game
// indicated by the integer key.
void selectionSort(Player** list, int low, int high, int key) {

    // i is the position we're filling.
    for (int i=low; i<high; i++) {

        // Best we've seen.
        int cur = i;

        // Update best.
        for (int j=i+1; j<=high; j++)
            if (compare(list[j], list[cur], key) < 0)
                cur = j;

        // Swap best into location i.
        swap(list, i, cur);
    }

}

// Swaps list[i] and list[j].
void swap(Player** list, int i, int j) {
    Player* tmp = list[i];
    list[i] = list[j];
    list[j] = tmp;
}