// Arup Guha
// 10/16/2025
// Solution to COP 3502 Program 4B: Rank List via Quick Sort

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.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;

// Functions dealing with a Player.
void initPlayer(Player* ptr, char* pName);
void update(Player* ptr, int key, int score);
int compare(Player* ptrP1, Player* ptrP2, int key);

// Functions for quick sort.
void quickSort(Player** list, int n, int key);
void quickSortRec(Player** list, int low, int high, int key);
int partition(Player** list, int low, int high, int key);
int getPartitionIndex(Player** list, int low, int high, int key);

// My auxiliary sort and swap function.
void insertionSort(Player** list, int low, int high, int key);
void swap(Player** list, int i, int j);

// Makes printing easy.
void printPlayer(Player* ptr, int rank, int key);

int main() {

    // For Partition function...
    srand(time(0));

    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!
    quickSort(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);
}

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

// Recursively Quick Sorts list[low..high] base don key.
void quickSortRec(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) {
        insertionSort(list, low, high, key);
        return;
    }

    // Run partition and return the index the subarray was split on.
    int split = partition(list, low, high, key);

    // Recursively sort left of partition.
    quickSortRec(list, low, split-1, key);

    // And right of partition.
    quickSortRec(list, split+1, high, key);
}

// Runs a partition on list[low..high]. The partition element is
// chosen via the median of 3 strategy.
int partition(Player** list, int low, int high, int key) {

    // Returns the partition index we should use for this partition.
    int partIdx = getPartitionIndex(list, low, high, key);

    // Swap the partition index into position low.
    swap(list, low, partIdx);

    // i is index to left side, j to the right side.
    int i = low+1, j = high;

    // Go till our low index and high index have crossed over.
    while (i<=j) {

        // Move left index.
        while (i<=j && compare(list[i], list[low], key) < 0) i++;

        // Move right index.
        while (j>=low && compare(list[low], list[j], key) < 0) j--;

        // If the pointers haven't crossed over, swap.
        if (i<j) swap(list, i, j);
    }

    // Index j is where the partition index needs to be.
    swap(list, low, j);

    // This is the partition index.
    return j;
}

// Uses Median of three strategy to find a partition index for list[low..high]
// If high-low < 2, then low is returned.
int getPartitionIndex(Player** list, int low, int high, int key) {

    // There aren't 3 items to pick from.
    if (high-low < 2) return low;

    // Pick 3 random values. Don't worry about repeats.
    int idx[3];
    for (int i=0; i<3; i++)
        idx[i] = low + rand()%(high-low+1);

    // item in idx[0] bigger than item in idx[1].
    if (compare( list[idx[0]], list[idx[1]], key) < 0 ) {

        // item in idx[1] bigger than item in idx[2]
        if (compare( list[idx[1]], list[idx[2]], key) < 0 )
            return idx[1];

        // If we're here idx[1] is the smallest. So we want the smaller of idx[0] and idx[2]
        if (compare( list[idx[0]], list[idx[2]], key) < 0 )
            return idx[2];

        // Smaller of idx[2] and idx[0].
        return idx[0];
    }

    // item in idx[1] is bigger than the item in idx[0].
    else {

        // item in idx[0] bigger than item in idx[2]
        if (compare( list[idx[0]], list[idx[2]], key) < 0 )
            return idx[0];

        // If we're here idx[0] is the smallest. So we want the smaller of idx[1] and idx[2]
        if (compare( list[idx[1]], list[idx[2]], key) < 0 )
            return idx[2];

        // Smaller of idx[1] and idx[2].
        return idx[1];

    }
}

// 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 Insertion Sort in the subarray list[low..high] based on the game
// indicated by the integer key.
void insertionSort(Player** list, int low, int high, int key) {

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

        // Swap until we're in the right place.
        for (int j=i; j>low; j--) {

            // See if item in index j needs to swap with previous index or not.
            if (compare(list[j], list[j-1], key) < 0)
                swap(list, j, j-1);

            // We need to get out.
            else
                break;

        }
    }
}

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