#3248. 「USACO 2020.1 Platinum」Falling Portals

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ksyx

题目描述

题目来自 USACO 2020 January Contest, Platinum Problem 3. Falling Portals

N 个世界,每个世界有一个传送门。初始时,世界 i (对于 1\le i\le N )位于 x 坐标 i y 坐标 A_i 。每个世界里还有一头奶牛。在时刻 0 ,所有的 y 坐标各不相同,然后这些世界开始坠落:世界 i 沿着 y 轴负方向以 i 单位每秒的速度移动。

在任意时刻,如果两个世界在某一时刻 y 坐标相同(可能是非整数时刻),传送门之间就会「同步」,使得其中一个世界的奶牛可以选择瞬间传送到另一个世界。

对于每一个 i ,在世界 i 的奶牛想要去往世界 Q_i 。帮助每头奶牛求出如果她以最优方案移动需要多少时间。

每个询问的输出是一个分数 a/b,其中 a b 为互质的正整数,或者 −1 ,如果不可能到达。

输入格式

输入的第一行包含一个整数 N

下一行包含 N 个空格分隔的整数 A_1,A_2,\ldots ,A_N

下一行包含 N 个空格分隔的整数 Q_1,Q_2,\ldots ,Q_N

输出格式

输出 N 行,第 i 行包含奶牛 i 的旅程的时间。

样例

样例输入

4
3 5 10 2
3 3 2 1

样例输出

7/2
7/2
5/1
-1

样例解释

考虑原先在世界 2 的奶牛的答案。在时刻 2 世界 1 和世界 2 同步,所以奶牛可以前往世界 1 。在时刻 7/2 世界 1 和世界 3 同步,所以奶牛可以前往世界 3

数据范围与提示

对于全部测试点, 2\le N\le 2\cdot 10^5,1\le A_i\le 10^9,Q_i\neq i

测试点 2,3 满足 N\le 100

测试点 4,5 满足 N\le 2\cdot 10^3

测试点 6\sim 14 没有额外限制。