AT_abc360_d.[ABC360D] Ghost Ants

入门

通过率：0%

AC君温馨提醒

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

题目描述

在数轴上有 $N$ 只蚂蚁，编号为 $1$ 到 $N$ 。第 $i$ 只蚂蚁（ $1 \leq i \leq N$ ）初始时位于坐标 $X_i$ ，并朝着正方向或负方向。所有蚂蚁的初始坐标互不相同。每只蚂蚁朝向由一个长度为 $N$ 的 $01$ 字符串 $S$ 表示，若 $S_i$ 为 0，则第 $i$ 只蚂蚁朝负方向，若 $S_i$ 为 1，则朝正方向。

现在为时刻 $0$ ，在接下来的 $(T+0.1)$ 单位时间内， $N$ 只蚂蚁以每单位时间 $1$ 的速度，分别朝各自的方向移动。当多只蚂蚁到达同一坐标时，它们会直接错身而过，不改变方向和速度。 $(T+0.1)$ 单位时间后，所有蚂蚁停止。

请计算满足 $1 \leq i < j \leq N$ ，在现在到时刻 $(T+0.1)$ 之间，第 $i$ 只蚂蚁和第 $j$ 只蚂蚁会相遇的整数对 $(i, j)$ 的数量。

输入格式

输入按以下格式从标准输入给出。

$N$ $T$ $S$ $X_1$ $X_2$ ... $X_N$

输出格式

请输出答案。

输入输出样例

输入#1
```
6 3
101010
-5 -1 0 1 2 4
```
输出#1
```
5
```

输入#2

13 656320850
0100110011101
-900549713 -713494784 -713078652 -687818593 -517374932 -498415009 -472742091 -390030458 -379340552 -237481538 -44636942 352721061 695864366

输出#2

说明/提示

限制条件

$2 \leq N \leq 2 \times 10^{5}$
$1 \leq T \leq 10^{9}$
$S$ 是由 0 和 1 组成的长度为 $N$ 的字符串
$-10^{9} \leq X_i \leq 10^{9}$ （ $1 \leq i \leq N$ ）
$X_i \neq X_j$ （ $1 \leq i < j \leq N$ ）
$N,T,X_i$ （ $1 \leq i \leq N$ ）均为整数

样例解释 1

以下 $5$ 对蚂蚁会相遇：

蚂蚁 $3$ 和蚂蚁 $4$ 在时刻 $0.5$ 相遇。
蚂蚁 $5$ 和蚂蚁 $6$ 在时刻 $1$ 相遇。
蚂蚁 $1$ 和蚂蚁 $2$ 在时刻 $2$ 相遇。
蚂蚁 $3$ 和蚂蚁 $6$ 在时刻 $2$ 相遇。
蚂蚁 $1$ 和蚂蚁 $4$ 在时刻 $3$ 相遇。
除此之外，没有其他蚂蚁组合会相遇，因此输出 $5$ 。

由 ChatGPT 4.1 翻译

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

首页