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

// 声明 ask 函数，按照题目要求
std::vector<int> ask(std::vector<int> a, std::vector<int> b);

int richest(int N, int T, int S) {
    if (N == 1) {
        // 只有一个客户时，直接返回该客户编号
        return 0;
    }

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

    // 记录已使用的请求数和查询次数
    int t_used = 0;
    int s_used = 0;

    // 备用列表用于存储下一轮的候选者
    std::vector<int> next_candidates;
    next_candidates.reserve(N / 2 + 1);

    while(candidates.size() > 1){
        next_candidates.clear();

        std::vector<int> a;
        std::vector<int> b;
        a.reserve(candidates.size() / 2);
        b.reserve(candidates.size() / 2);

        // 将候选者成对分组
        int i = 0;
        for(; i + 1 < candidates.size(); i += 2){
            a.push_back(candidates[i]);
            b.push_back(candidates[i + 1]);
        }

        // 如果候选者数量为奇数，最后一个候选者直接进入下一轮
        bool has_carry_over = false;
        int carry_over = -1;
        if(i < candidates.size()){
            has_carry_over = true;
            carry_over = candidates[i];
        }

        // 更新已使用的请求数和查询次数
        t_used += 1;
        s_used += a.size();

        // 检查是否超过限制
        if(t_used > T || s_used > S){
            // 超过限制时，可尝试返回当前最好的候选者
            // 这里假设返回当前候选者中的第一个
            return candidates[0];
        }

        // 发送当前批次的比较请求
        std::vector<int> winners = ask(a, b);

        // 将获胜者加入下一轮的候选者列表
        for(auto &winner : winners){
            next_candidates.push_back(winner);
        }

        // 如果有携带者，加入下一轮
        if(has_carry_over){
            next_candidates.push_back(carry_over);
        }

        // 交换候选者列表，进行下一轮
        candidates.swap(next_candidates);
    }

    // 返回最后剩下的候选者，即为存款最多的客户
    return candidates[0];
}