Skip to content

1465: T2

题目

题目描述

2022年2月4日,第24届冬季奥林匹克运动会在北京开幕。Kerbin星球上也在举行这冬奥会,不同的是,他们的冬奥会上有一个奇怪的项目。暂且不用关心这个项目比什么,更重要的是它的赛制规则。

有$n$名选手参赛,为了比赛正常进行,保证$n$是$2$的次幂($n=2^k$)。提供每一位选手的基本参赛信息,特别的,由于每一位选手都是身经百战的老手,很容易得知每个人的平均水平,我们用一个整数来评估。比赛开始前,$n$名选手按照给定的顺序依次排列,并且所有的选手被视作在同一小组比赛。接下来这个包含所有选手的小组开始比赛,参赛选手按照初始顺序相邻的两名选手展开比赛,其中获胜的选手进入优胜组,败北的选手进入劣汰组。在每个新产生的小组中,选手按照在原小组顺位的优先级排列, 例如两个获胜的选手同时进入优胜组,原来小组里排在前面的选手在优胜组依然排在另一个选手之前。等上一轮的所有比赛结束之后,比赛轮数加$1$,特别的,规定比赛开始之前的轮数为$0$。下一轮的比赛在上一轮产生的所有小组中分别按照如上的规则进行。

fig

为了方便理解,具体过程如上图所示,每一个小框代表一个小组,在一轮比赛之后分别产生两个新的小组。由于保证$n$是$2$的次幂,所以比赛能够一直进行下去。如果每次把获胜的小组排在淘汰的小组之前,最后会产生一个新的排序,作为最终排名。

小T是这项运动的爱好者,他收集到了这次冬奥会所有选手的参赛信息,平均水平和初始参赛排位。他想要在比赛之前按照选手的平均水平预估比赛结果。为方便预估,认为平均水平高的选手获胜(如果水平相同,排在靠前位置的选手获胜)。请给出最终的排名,如果选手人数超过$30$,则只要给出排名前$30$的名单。此外,小T会给出$q$个询问,每个询问包含两个选手编号(选手按照初始参赛排位编号1-based)$x$和$y$($x$可能等于$y$),请给出这两名选手最后一次分在同一小组是在第几轮比赛。

输入格式

第一行一个正整数$n$,参赛的选手数。

接下来$n$行,每行一个字符串包含一名选手的信息,其中姓名,国籍,年龄,平均水平以"_"隔开

具体参考样例输入,保证姓名和国籍只包含字母且长度分别不超过10年龄和平均水平为不超过100的非负整数

第$n+2$行一个正整数$q$,询问数。

接下来$q$行,每行两个整数$x$和$y$ ($1\le x,y\le n$),表示询问的选手编号。

输出格式

前$\min(n,30)$行,每行一个字符串。

第$i$行表示排名为$i$的选手信息,格式为Rank xxx: name-xxx nation-xxx age-xxxxxx填入内容,具体见样例输出。

接下来$q$行,每行一个整数,表示询问的两个选手最后一次同组的比赛轮数。

样例输入

```text 4 Alice_Germany_20_10 Bob_China_19_13 Carol_Norway_21_8 Dave_Sweden_22_15 3 1 2 1 3 1 4

```

样例输出

```text Rank 1: name-Dave nation-Sweden age-22 Rank 2: name-Bob nation-China age-19 Rank 3: name-Alice nation-Germany age-20 Rank 4: name-Carol nation-Norway age-21 0 1 0

```

数据范围

样例说明

  • 第$0$轮排名:Alice, Bob, Carol, Dave
  • 第$1$轮排名:Bob, Dave, Alice, Carol
  • 第$2$轮排名:Dave, Bob, Alice, Carol
  • 比赛结束

对于$20\%$的数据,$n=2^{11}$,$q=0$

对于另外$20\%$的数据,$n=2^{17}$,$q=0$

对于另外$20\%$的数据,$n=2^{17}$,$q=1$

对于另外$20\%$的数据,$n=2^{17}$,$q\le 10^5$

对于所有数据,$n=2^{17}$,$q\le 2\times10^6$

提醒

  • 由于询问数$q$可能非常大,建议整数使用scanfprintf输入输出,避免io造成的超时。
  • 如果要使用cincout,请在输入输出之前添加ios::sync_with_stdio(false);语句,并且用\n替换endl

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!