102991: [Atcoder]ABC299 B - Trick Taking

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：9 Solved：0

Description

Score : $200$ points

Problem Statement

$N$ players with ID numbers $1, 2, \ldots, N$ are playing a card game.
Each player plays one card.

Each card has two parameters: color and rank, both of which are represented by positive integers.
For $i = 1, 2, \ldots, N$, the card played by player $i$ has a color $C_i$ and a rank $R_i$. All of $R_1, R_2, \ldots, R_N$ are different.

Among the $N$ players, one winner is decided as follows.

  • If one or more cards with the color $T$ are played, the player who has played the card with the greatest rank among those cards is the winner.
  • If no card with the color $T$ is played, the player who has played the card with the greatest rank among the cards with the color of the card played by player $1$ is the winner. (Note that player $1$ may win.)

Print the ID number of the winner.

Constraints

  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq T \leq 10^9$
  • $1 \leq C_i \leq 10^9$
  • $1 \leq R_i \leq 10^9$
  • $i \neq j \implies R_i \neq R_j$
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $T$
$C_1$ $C_2$ $\ldots$ $C_N$
$R_1$ $R_2$ $\ldots$ $R_N$

Output

Print the answer.

Sample Input 1

4 2
1 2 1 2
6 3 4 5

Sample Output 1

4

Cards with the color $2$ are played. Thus, the winner is player $4$, who has played the card with the greatest rank, $5$, among those cards.

Sample Input 2

4 2
1 3 1 4
6 3 4 5

Sample Output 2

1

No card with the color $2$ is played. Thus, the winner is player $1$, who has played the card with the greatest rank, $6$, among the cards with the color of the card played by player $1$ (color $1$).

Sample Input 3

2 1000000000
1000000000 1
1 1000000000

Sample Output 3

1

Input

题意翻译

## 题意简述 有 $n$ 个玩家编号分别为 $1,2,\cdots,n$正在玩纸牌游戏。但他们不知道谁是赢家。请你判断胜利的玩家的编号。 每个玩家的牌都有两个属性：颜色 $c_i$ 和点数 $r_i$。裁判会提前抽取一张牌，其颜色为 $t$。 如果玩家手上有颜色为 $t$ 的牌，那么赢家就是拥有颜色为 $t$ 的牌且点数最大的玩家。 否则，赢家就是颜色为 $c_1$ 的牌且点数最大的玩家。 Translate by @[tianbiandeshenghuo11](/user/752485)

Output

分数：$200$分 部分 问题描述 具有ID号码 $1, 2, \ldots, N$的$N$名玩家正在进行一场纸牌游戏。 每个玩家出一张牌。 每张牌有两个参数：颜色和等级，都用正整数表示。 对于$i = 1, 2, \ldots, N$，玩家$i$出的牌具有颜色$C_i$和等级$R_i$。 所有$R_1, R_2, \ldots, R_N$都不同。 在$N$名玩家中，按照以下方式决定一名获胜者。
  • 如果出了颜色为$T$的牌，那么出颜色为$T$的牌中等级最高的人是获胜者。
  • 如果没有出颜色为$T$的牌，那么出玩家$1$出牌的颜色的牌中等级最高的人是获胜者。注意玩家$1$可能获胜。
打印获胜者的ID号码。 部分 约束
  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq T \leq 10^9$
  • $1 \leq C_i \leq 10^9$
  • $1 \leq R_i \leq 10^9$
  • $i \neq j \implies R_i \neq R_j$
  • 输入中的所有值都是整数。
部分 输入 输入将以以下格式从标准输入给出： $N$ $T$ $C_1$ $C_2$ $\ldots$ $C_N$ $R_1$ $R_2$ $\ldots$ $R_N$ 部分 输出 打印答案。 部分 样例输入 1 
4 2
1 2 1 2
6 3 4 5
部分 样例输出 1 
4
出了颜色为$2$的牌。 因此，获胜者是玩家$4$，他出的牌在那些牌中等级最高，为$5$。 部分 样例输入 2 
4 2
1 3 1 4
6 3 4 5
部分 样例输出 2 
1
没有出颜色为$2$的牌。 因此，获胜者是玩家$1$，他出的牌在颜色为玩家$1$出牌的颜色（颜色$1$）的牌中等级最高，为$6$。 部分 样例输入 3 
2 1000000000
1000000000 1
1 1000000000
部分 样例输出 3 
1

HINT

颜色跟t相同的最大排名是谁？如果没有颜色t，那么跟1号颜色相同的排名最大是谁？

Source/Category

加入题单

算法标签：