AT_joig2024_c.座席 2 (Seats 2)

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在 JOI 国，今年将举办一场编程世界大赛。预计有 $N$ 名选手参加，每位选手从 $1$ 到 $N$ 编号。

每位选手的国籍由一个 $1$ 到 $10^9$ 之间的整数表示，第 $i$ 位选手（ $1 \leq i \leq N$ ）的国籍为 $C_i$ 。保证 $N$ 名选手中，国籍并不全相同。此外，每位选手的座位排成一条直线，第 $i$ 位选手（ $1 \leq i \leq N$ ）的座位位于 $X_i$ 位置。第 $i$ 位选手和第 $j$ 位选手之间的座位距离为 $|X_i - X_j|$ ，其中 $|x|$ 表示 $x$ 的绝对值。

在比赛期间，每位选手希望知道与自己国籍不同的选手中，离自己座位最近的那一位选手到底有多远。

给出每位选手的国籍和座位位置的信息，请你编写程序，对于每位选手 $i$ ，求出与其国籍不同且距离最近的选手，到自己的座位的距离。

输入格式

输入按照以下格式给出：

$N$
$C_1$ $X_1$
$C_2$ $X_2$
$\vdots$
$C_N$ $X_N$

输出格式

输出共 $N$ 行。第 $i$ 行（ $1 \leq i \leq N$ ）输出与第 $i$ 位选手国籍不同的选手中，座位距离最小的那一位选手，到第 $i$ 位选手座位的距离。

输入输出样例

输入#1
```
3
2 5
1 1
1 2
```
输出#1
```
3
4
3
```
输入#2
```
5
1 1
2 4
2 14
3 10
2 2
```
输出#2
```
1
3
4
4
1
```
输入#3
```
3
1 1
2 1
1 1
```
输出#3
```
0
0
0
```

说明/提示

子任务

（ $20$ 分） $N \leq 1000$ 。
（ $40$ 分） $C_i \leq 10$ （ $1 \leq i \leq N$ ）。
（ $40$ 分）无其他附加限制。

样例解释 1

第 1 位选手的国籍为 $2$ ，与其国籍不同的选手为第 $2, 3$ 位。在这些选手中，距离第 1 位选手最近的是第 3 位，距离为 $3$ 。所以第 1 行输出 $3$ 。

第 2 位选手的国籍为 $1$ ，与其国籍不同的选手只有第 1 位。其与第 1 位选手的距离为 $4$ ，因此第 2 行输出 $4$ 。

第 3 位选手的国籍为 $1$ ，与其国籍不同的选手只有第 1 位。其与第 1 位选手的距离为 $3$ ，因此第 3 行输出 $3$ 。

该输入样例满足子任务 $1, 2, 3$ 的限制。

样例解释 2

该输入样例满足子任务 $1, 2, 3$ 的限制。

样例解释 3

也可能存在多个选手的座位在同一位置。

该输入样例满足子任务 $1, 2, 3$ 的限制。

约束条件

$2 \leq N \leq 300,\!000$ 。
$1 \leq C_i \leq 10^9$ （ $1 \leq i \leq N$ ）。
$1 \leq X_i \leq 10^9$ （ $1 \leq i \leq N$ ）。
所有 $N$ 名选手国籍不会全部相同。
输入的所有值均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页