PID551 / [IOI09]Archery
题目描述

一场箭术比赛规则如下所示。在一条直线上排着N个靶子,靶子从左到右序号依次为从1到N。同时有2N个选手,在比赛的任何时刻,同一个靶位上都有两个选手。比赛的每一轮按照如下规则进行:

在同一个靶位的两位选手比赛一场决出胜者,然后所有选手按照如下规则移动:

在2到N号靶位上的胜者移动到他们的左侧的靶位(即分别移动到1到N-1号靶位)

在2到N号靶位上的负者,以及1号靶位上的胜者,停留在同一个靶位。

1号靶位上的负者移动到N号靶位。

这场比赛持续R轮(R>=2N)。

你作为唯一一个准时到达的选手(其他选手已经提前到达了并且排成了一行),你现在要做的就是插入这个队伍,在你进入队伍后,队列中前两个选手将对应一号靶位,接下来两个将对应二号靶位,以此类推。

所有的选手(包括你)都用一个数值衡量技术水平,在同一个靶位上,数值比较小的选手会成为胜者,没有两个选手的技术水平相同。

在了解了所有选手的技术水平之后,你需要找到一个位置插入使得你最终对应的靶位序号尽量小,在此前提下,你希望你初始时对应的靶位序号尽量大。

数据规模

1<=N<=200000

2*N<=R<=1000000000

每个测试点2s

输入格式

第一行包含整数N和R。

接下来2*N行给出了选手的等级。第一行是你的等级,其余各行是其他选手的等级。每个选手一行,按照他们已经排好的顺序(从左到右)。这2*N行每行包含一个1~2*N的整数,1表示最好,2*N表示最差。没有两个选手的等级相同。

输出格式

一个1~N的整数,表示你在开始比赛时所在的靶位。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论