Quantum Moochanics

题目描述

在空闲时间里，Bessie 喜欢涉足实验物理。她最近发现了一对新的亚原子粒子，分别叫做 mootrinos 和 antimootrinos。和标准的物质-反物质对一样，mootrinos 与 antimootrinos 相遇时会相互湮灭并消失。

但这些粒子的独特之处在于：每当 Bessie 观察它们时，它们会在保持速度不变的情况下切换运动方向。

在她最新的实验中，Bessie 将偶数个 $N$（$2 \leq N \leq 2 \cdot 10^5$）这样的粒子放在一条直线上。直线最左边是一个 mootrino，之后两种粒子交替出现，第 $i$ 个粒子位于位置 $p_i$（$0 \leq p_1 < \cdots < p_N \leq 10^{18}$）。mootrinos 初始向右运动，而 antimootrinos 初始向左运动，并且第 $i$ 个粒子以恒定速度 $s_i$ 个单位/秒运动（$1 \leq s_i \leq 10^9$）。

Bessie 在如下时刻进行观察： 首先，在实验开始后 $1$ 秒。 然后，在第一次观察后 $2$ 秒。 然后，在第二次观察后 $3$ 秒。 ... 然后，在第 $n$ 次观察后 $n + 1$ 秒。

每次观察时，Bessie 会记录哪些粒子已经消失。这个实验可能需要极长时间才能完成，因此 Bessie 希望先模拟其实验结果。给定实验设置，请你帮助 Bessie 确定她会在何时（即第几次观察）观察到每个粒子消失！可以证明所有粒子最终都会消失。

输入格式

每个输入包含 $T$（$1\le T\le 10$）个相互独立的测试用例。

每个测试用例由三行组成。第一行包含 $N$，第二行包含 $p_1,\dots,p_N$，第三行包含 $s_1\dots,s_N$。 保证所有测试用例的 $N$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每个测试用例，输出每个粒子消失时对应的观察编号，用空格分隔。

4
2
1 11
1 1
2
1 12
1 1
2
1 11
4 6
2
1 11
4 5

9 9
11 11
1 1
3 3

2
4
1 3 5 8
1 1 1 1
4
1 4 5 8
1 1 1 1

1 1 3 3
7 2 2 7

提示

对于第一个测试用例，Bessie 在前 $8$ 次观察中看到如下情况： 第一个 mootrino（初始向右运动）显示在位置 $2 \rightarrow 0 \rightarrow 3 \rightarrow -1 \rightarrow 4 \rightarrow -2 \rightarrow 5 \rightarrow -3$。 第一个 antimootrino（初始向左运动）显示在位置 $10 \rightarrow 12 \rightarrow 9 \rightarrow 13 \rightarrow 8 \rightarrow 14 \rightarrow 7 \rightarrow 15$。 随后恰在第 $9$ 次观察时，这两个粒子在位置 $6$ 相遇并相互湮灭。

对于第二个测试用例，antimootrino 的起始位置额外向右偏了 $1$ 个单位，因此两粒子在第 $11$ 次观察前的半秒于位置 $6.5$ 相遇。 注意我们只关心观察编号，而不关心时间或位置。

对于第一个测试用例： 最左边的两个粒子恰在第 $1$ 次观察时于位置 $2$ 相遇。 最右边的两个粒子在第 $3$ 次观察前的半秒于位置 $6.5$ 相遇。

计分（SCORING）： 输入 3 满足 $N = 2$。 输入 4 满足 $N \leq 2000$ 且对所有奶牛有 $p_i \leq 10^4$。 输入 5-7 满足 $N \leq 2000$。 输入 8-12 没有额外限制。

题目来源：Aryansh Shrivastava, Benjamin Qi

标签: USACO|2024|Gold

来源

USACO|2024|Gold