QOJ.ac

QOJ

Límite de tiempo: 1 s Límite de memoria: 256 MB Puntuación total: 100

#6429. 一起来玩冰壶

Estadísticas

冰壶是一项运动员在冰面上将冰壶滑向目标区域的运动。距离目标区域中心最近的队伍获胜。

两支队伍,红队和蓝队,在数轴上进行比赛。比赛结束后,数轴上剩余 $(n + m)$ 个冰壶,其中 $n$ 个属于红队,另外 $m$ 个属于蓝队。红队的第 $i$ 个冰壶位于 $a_i$,蓝队的第 $j$ 个冰壶位于 $b_j$。

设 $c$ 为目标区域中心的位置。根据上述描述,如果存在某个 $i$($1 \le i \le n$),使得对于所有 $1 \le j \le m$,都有 $|c - a_i| < |c - b_j|$,则红队获胜。此外,如果满足该条件的 $i$ 的数量恰好为 $p$,则称红队得 $p$ 分。

给定红队和蓝队冰壶的位置,你的任务是确定目标区域中心 $c$ 的位置,使得红队获胜并获得尽可能高的分数。注意 $c$ 可以是任何实数,不一定是整数。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$,表示测试数据的组数。对于每组测试数据:

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$),分别表示红队和蓝队冰壶的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$),表示红队冰壶的位置。

第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$ ($1 \le b_i \le 10^9$),表示蓝队冰壶的位置。

保证所有测试数据中 $n$ 之和与 $m$ 之和均不超过 $5 \times 10^5$。

输出格式

对于每组测试数据,输出一行。如果存在某个 $c$ 使得红队获胜并获得尽可能高的分数,输出一个整数,表示红队可能获得的最大分数(不是 $c$ 的值)。否则,输出 “Impossible”。

样例

样例输入 1

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

样例输出 1

2
3
Impossible

说明

对于第一个样例,我们可以令 $c = 2.5$,这样位置在 2 和 3 的红队冰壶得分。

对于第二个样例,我们可以令 $c = 7$,这样位置在 5 和 7 的红队冰壶得分。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.