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

// 声明 ask 函数，根据题目要求，这个函数由交互库提供
std::vector<int> ask(std::vector<int> a, std::vector<int> b);

// 实现 richest 函数
int richest(int N, int T, int S) {
    // 定义一个阈值，用于决定使用哪种方法
    const int SMALL_N_THRESHOLD = 1000;

    if (N <= SMALL_N_THRESHOLD) {
        // 小范围数据处理（例如 N <= 1000）
        // 方法：进行所有可能的两两比较

        // 生成所有不同的客户对 (i, j) 其中 i < j
        std::vector<int> a;
        std::vector<int> b;
        a.reserve((N * (N - 1)) / 2);
        b.reserve((N * (N - 1)) / 2);
        
        for(int i = 0; i < N; ++i){
            for(int j = i + 1; j < N; ++j){
                a.push_back(i);
                b.push_back(j);
            }
        }

        // 检查是否超过查询次数限制
        if (a.size() > S || T < 1) {
            // 无法满足查询次数或请求次数限制
            // 这里假设返回 -1 表示无法确定
            return -1;
        }

        // 发送一次请求
        std::vector<int> winners = ask(a, b);

        // 统计每个客户赢得的次数
        std::vector<int> win_count(N, 0);
        for(auto winner : winners){
            if(winner >= 0 && winner < N){
                win_count[winner]++;
            }
        }

        // 找到胜利次数最多的客户
        int richest_customer = 0;
        for(int i = 1; i < N; ++i){
            if(win_count[i] > win_count[richest_customer]){
                richest_customer = i;
            }
        }

        return richest_customer;

    } else {
        // 大范围数据处理（例如 N > 1000）
        // 方法：采用淘汰赛的方式

        // 初始化所有客户为候选者
        std::vector<int> candidates;
        candidates.reserve(N);
        for(int i = 0; i < N; ++i){
            candidates.push_back(i);
        }

        int remaining_requests = T;
        int remaining_queries = S;

        while(candidates.size() > 1 && remaining_requests > 0 && remaining_queries > 0){
            std::vector<int> a;
            std::vector<int> b;

            size_t i = 0;
            size_t size = candidates.size();
            // 生成当前轮的比较对
            for(; i + 1 < size && (a.size() < static_cast<size_t>(remaining_queries)); i += 2){
                a.push_back(candidates[i]);
                b.push_back(candidates[i+1]);
            }

            // 如果本轮没有比较对（可能由于剩余查询次数不足），则无法继续
            if(a.empty()){
                break;
            }

            // 发送请求
            std::vector<int> winners = ask(a, b);

            // 更新剩余查询次数和请求次数
            int queries_used = a.size();
            remaining_queries -= queries_used;
            remaining_requests -= 1;

            // 更新候选者为胜者
            std::vector<int> new_candidates;
            new_candidates.reserve((size + 1) / 2); // 预估大小
            for(auto winner : winners){
                if(winner >= 0 && winner < N){
                    new_candidates.push_back(winner);
                }
            }

            // 如果当前轮有奇数个候选者，保留最后一个候选者
            if(i < size){
                new_candidates.push_back(candidates[size - 1]);
            }

            // 更新候选者列表
            candidates = std::move(new_candidates);
        }

        // 如果最后剩下一个候选者，则返回该候选者
        if(candidates.size() == 1){
            return candidates[0];
        }

        // 如果无法通过淘汰赛确定，返回第一个候选者或其他策略
        // 这里选择返回第一个候选者
        if(!candidates.empty()){
            return candidates[0];
        }

        // 如果没有候选者，返回 -1 表示无法确定
        return -1;
    }
}