AT_abc188_c [ABC188C] ABC Tournament

题目描述

有 $2^N$ 名选手，从选手 $1$ 到选手 $2^N$，将以淘汰赛的形式进行编程对决。
选手 $i$ 的评分为 $A_i$。任意两名选手的评分都不相同，且每次对决时，评分较高的选手必定获胜。

比赛的赛程为完全二叉树的形式。
更准确地说，比赛按照以下方式进行：

• 对于 $i=1,2,3,\dots,N$，依次进行如下操作：

  • 对于每个整数 $j$（$1\le j\le 2^{N-i}$），在尚未被淘汰的选手中，第 $2j-1$ 小的编号选手与第 $2j$ 小的编号选手进行对决。

请输出获得亚军（即在最后一场比赛中失败的选手）的编号。

输入格式

输入通过标准输入给出，格式如下：

$N$ $A_1$ $A_2$ $A_3$ $\dots$ $A_{2^N}$

输出格式

请输出获得亚军的选手编号。

输入输出样例 #1

输入 #1

2
1 4 2 5

输出 #1

2

输入输出样例 #2

输入 #2

2
3 1 5 4

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

2

说明/提示

限制条件

• $1\le N\le 16$
• $1\le A_i\le 10^9$
• $A_i$ 互不相同
• 输入中的所有值均为整数

样例解释 1

首先，选手 $1$ 与 $2$，选手 $3$ 与 $4$ 分别对决，根据评分高低，选手 $2$ 和 $4$ 获胜。
接着，选手 $2$ 与选手 $4$ 对决，选手 $4$ 获胜，比赛结束。
最后一场比赛中失败的是选手 $2$，因此输出 $2$。

样例解释 2

首先，选手 $1$ 与 $2$，选手 $3$ 与 $4$ 分别对决，根据评分高低，选手 $1$ 和 $3$ 获胜。
接着，选手 $1$ 与选手 $3$ 对决，选手 $3$ 获胜，比赛结束。
最后一场比赛中失败的是选手 $1$，因此输出 $1$。

由 ChatGPT 4.1 翻译