#include "richest.h"
#include <vector>
#include <algorithm>

// Declaration of the ask function as specified
std::vector<int> ask(std::vector<int> a, std::vector<int> b);

// Function to find the richest customer
int richest(int N, int T, int S) {
    // Threshold to switch strategies
    const int SMALL_N_THRESHOLD = 1000;

    // If N is small, use the brute-force approach
    if (N <= SMALL_N_THRESHOLD) {
        std::vector<int> a;
        std::vector<int> b;
        a.reserve((N * (N - 1)) / 2);
        b.reserve((N * (N - 1)) / 2);

        // Generate all possible unique pairs (i, j) where i < j
        for (int i = 0; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                a.push_back(i);
                b.push_back(j);
            }
        }

        // Make a single request with all pairs
        std::vector<int> responses = ask(a, b);

        // Count the number of wins for each customer
        std::vector<int> win_counts(N, 0);
        for (const int& winner : responses) {
            ++win_counts[winner];
        }

        // Find the customer with the maximum win count
        int richest_customer = 0;
        int max_wins = win_counts[0];
        for (int i = 1; i < N; ++i) {
            if (win_counts[i] > max_wins) {
                max_wins = win_counts[i];
                richest_customer = i;
            }
        }

        return richest_customer;
    }
    // For larger N, use a grouped approach
    else {
        // Define the number of groups. Reserve one request for each group.
        // The remaining requests will be used to determine the global maximum.
        // To maximize efficiency, set group_count to 10, leaving 10 requests for finding the global maximum.
        const int GROUP_COUNT = 10;
        int group_size = (N + GROUP_COUNT - 1) / GROUP_COUNT; // Ceiling division

        std::vector<int> local_maxima; // To store the maximum from each group

        // Step 1: Find the local maximum in each group
        for (int g = 0; g < GROUP_COUNT; ++g) {
            int start = g * group_size;
            int end = std::min(start + group_size, N);
            if (start >= end) {
                continue; // No elements in this group
            }

            int current = start; // Initialize current maximum for the group
            std::vector<int> a_vec;
            std::vector<int> b_vec;

            // Prepare comparisons within the group
            for (int i = start + 1; i < end; ++i) {
                a_vec.push_back(current);
                b_vec.push_back(i);
            }

            if (a_vec.empty()) {
                // Only one element in the group
                local_maxima.push_back(current);
                continue;
            }

            // Make a request to compare the current maximum with all other elements in the group
            std::vector<int> responses = ask(a_vec, b_vec);

            // The last response corresponds to the group maximum
            int group_max = responses.back();
            local_maxima.push_back(group_max);
        }

        // Step 2: Determine the global maximum among the local maxima
        // Initialize the global candidate as the first local maximum
        int global_max = local_maxima[0];

        // Compare the global candidate with each of the remaining local maxima
        for (size_t i = 1; i < local_maxima.size(); ++i) {
            std::vector<int> a_query = { global_max };
            std::vector<int> b_query = { local_maxima[i] };
            std::vector<int> response = ask(a_query, b_query);

            if (response[0] == local_maxima[i]) {
                // Update the global maximum if the current local maximum is richer
                global_max = local_maxima[i];
            }
            // If response[0] == global_max, do nothing as global_max remains
        }

        return global_max;
    }
}