← 返回题目列表

AtCoder · awc0007_c

C. 小组淘汰赛

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥正在举办一场问答比赛,其中 N 学生参与。

每个学生都会分配一个学生 ID 号 1 to N和学生 i 的测验技能等级为 A_i.

比赛开始时,所有 N 学生留下来,并根据以下规则重复“轮次”:

  • 将当前剩余的学生按照学号从小到大的顺序排列,分为 K 从前面。也就是说,第 1 个通过 K第 1 组中排列顺序的学生, (K{+}1)-th 通过 2K第 2 组表格,依此类推。如果最后一组的数量少于 K 学生,它仍然是一个具有该数量学生的单一群体。
  • 对于每个组,只有 1 该组中技能水平最高的学生幸存。如果有多位技能等级最高的学生,则其中学号最小的学生生存。 1 学生,那个学生照样生存。)
  • 如果只有 1 学生仍然存在,该学生被宣布为冠军,比赛结束。如果 2 或更多学生留下,只保留幸存的学生,我们返回步骤 1 进行下一轮。

每轮至少有 2 剩余的学生,并且自从 K \geq 2,至少一组包含 2 或更多学生,因此每轮剩余学生的数量都会严格减少。因此,比赛在有限轮数后结束。

确定最终赢得比赛的学生的学生 ID 号。

约束

  • 2 \leq N \leq 5 \times 10^5
  • 2 \leq K \leq N
  • 1 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入

N K
A_1 A_2 \ldots A_N
  • 第一行包含整数 N 代表学生人数和整数 K 代表每组的最大学生人数,以空格分隔。
  • 第二行包含整数 A_1, A_2, \ldots, A_N 代表每个学生的技能水平,以空格分隔。

输出

在一行上打印获胜学生的学生 ID 号。


示例输入 1

6 2
3 1 4 1 5 9

示例输出 1

6

示例输入 2

10 3
5 2 8 3 7 1 6 4 9 10

示例输出 2

10

示例输入 3

15 4
12 5 9 3 15 7 11 2 8 14 1 6 13 10 4

示例输出 3

5