#include "richest.h"

int richest(int N, int T, int S) {
    // 确定分组数量
    // 如果 T == 1，则所有比较必须在一次请求中完成
    // 否则，分为 K = T - 1 组，并留出一次请求用于比较局部最大值
    int K = (T > 1) ? T - 1 : 1;
    // 计算每组的大小，确保均匀分配
    int group_size = (N + K - 1) / K;

    vector<int> local_maxima; // 存储每组的局部最大值

    for(int k = 0; k < K; k++) {
        int start = k * group_size;
        int end = min(start + group_size, N);

        if(start >= end) continue;

        // 初始化当前组的最大值为第一个客户
        int current_max = start;

        // 准备比较的向量
        vector<int> a;
        vector<int> b;

        for(int i = start + 1; i < end; i++) {
            a.push_back(current_max);
            b.push_back(i);
        }

        // 发送请求并获取比较结果
        vector<int> res = ask(a, b);

        // 根据比较结果更新当前组的最大值
        for(int i = 0; i < res.size(); i++) {
            if(res[i] == b[i]) {
                current_max = b[i];
            }
            // 如果 res[i] == a[i]，current_max 保持不变
        }

        // 将当前组的局部最大值加入列表
        local_maxima.push_back(current_max);
    }

    // 如果只进行了 K=1 组的比较，直接返回该组的最大值
    if(local_maxima.size() == 1) {
        return local_maxima[0];
    }

    // 准备比较所有局部最大值以找到全局最大值
    // 初始化全局最大值为第一个局部最大值
    int global_max = local_maxima[0];
    vector<int> a_final;
    vector<int> b_final;

    for(int i = 1; i < local_maxima.size(); i++) {
        a_final.push_back(global_max);
        b_final.push_back(local_maxima[i]);
    }

    // 发送最终的比较请求
    vector<int> res_final = ask(a_final, b_final);

    // 根据比较结果更新全局最大值
    for(int i = 0; i < res_final.size(); i++) {
        if(res_final[i] == b_final[i]) {
            global_max = b_final[i];
        }
        // 如果 res_final[i] == a_final[i]，global_max 保持不变
    }

    return global_max;
}

answer.code: In function ‘int richest(int, int, int)’:
answer.code:11:5: error: ‘vector’ was not declared in this scope
   11 |     vector<int> local_maxima; // 存储每组的局部最大值
      |     ^~~~~~
answer.code:11:5: note: suggested alternatives:
In file included from /usr/include/c++/13/vector:66,
                 from richest.h:4,
                 from answer.code:1:
/usr/include/c++/13/bits/stl_vector.h:425:11: note:   ‘std::vector’
  425 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
/usr/include/c++/13/vector:86:13: note:   ‘std::pmr::vector’
   86 |       using vector = std::vector<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~~
answer.code:11:12: error: expected primary-expression before ‘int’
   11 |     vector<int> local_maxima; // 存储每组的局部最大值
      |            ^~~
answer.code:15:19: error: ‘min’ was not declared in this scope
   15 |         int end = min(start + group_size, N);
      |                   ^~~
answer.code:15:19: note: suggested alternatives:
In file included from /usr/include/c++/13/vector:62:
/usr/include/c++/13/bits/stl_algobase.h:281:5: note:   ‘std::min’
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
In file included from /usr/include/c++/13/tuple:44,
                 from /usr/include/c++/13/bits/uses_allocator_args.h:38,
                 from /usr/include/c++/13/bits/memory_resource.h:41,
                 from /usr/include/c++/13/vector:80:
/usr/include/c++/13/bits/ranges_util.h:733:29: note:   ‘std::ranges::min’
  733 |   inline constexpr __min_fn min{};
      |                             ^~~
answer.code:23:16: error: expected primary-expression before ‘int’
   23 |         vector<int> a;
      |                ^~~
answer.code:24:16: error: expected primary-expression before ‘int’
   24 |         vector<int> b;
      |                ^~~
answer.code:27:13: error: ‘a’ was not declared in this scope
   27 |             a.push_back(current_max);
      |             ^
answer.code:28:13: error: ‘b’ was not declared in this scope
   28 |             b.push_back(i);
      |             ^
answer.code:32:16: error: expected primary-expression before ‘int’
   32 |         vector<int> res = ask(a, b);
      |                ^~~
answer.code:35:28: error: ‘res’ was not declared in this scope
   35 |         for(int i = 0; i < res.size(); i++) {
      |                            ^~~
answer.code:36:26: error: ‘b’ was not declared in this scope
   36 |             if(res[i] == b[i]) {
      |                          ^
answer.code:43:9: error: ‘local_maxima’ was not declared in this scope
   43 |         local_maxima.push_back(current_max);
      |         ^~~~~~~~~~~~
answer.code:47:8: error: ‘local_maxima’ was not declared in this scope
   47 |     if(local_maxima.size() == 1) {
      |        ^~~~~~~~~~~~
answer.code:53:22: error: ‘local_maxima’ was not declared in this scope
   53 |     int global_max = local_maxima[0];
      |                      ^~~~~~~~~~~~
answer.code:54:12: error: expected primary-expression before ‘int’
   54 |     vector<int> a_final;
      |            ^~~
answer.code:55:12: error: expected primary-expression before ‘int’
   55 |     vector<int> b_final;
      |            ^~~
answer.code:58:9: error: ‘a_final’ was not declared in this scope
   58 |         a_final.push_back(global_max);
      |         ^~~~~~~
answer.code:59:9: error: ‘b_final’ was not declared in this scope
   59 |         b_final.push_back(local_maxima[i]);
      |         ^~~~~~~
answer.code:63:12: error: expected primary-expression before ‘int’
   63 |     vector<int> res_final = ask(a_final, b_final);
      |            ^~~
answer.code:66:24: error: ‘res_final’ was not declared in this scope
   66 |     for(int i = 0; i < res_final.size(); i++) {
      |                        ^~~~~~~~~
answer.code:67:28: error: ‘b_final’ was not declared in this scope
   67 |         if(res_final[i] == b_final[i]) {
      |                            ^~~~~~~