A5908. 「USACO 2020.1 Platinum」Falling Portals
编程题
省选/NOI-
知识点
题目描述
**题目来自 [USACO 2020 January Contest, Platinum](http://usaco.org/index.php?page=jan20results) Problem 3. [Falling Portals](http://usaco.org/index.php?page=viewproblem2&cpid=998)**
有 $N$ 个世界，每个世界有一个传送门。初始时，世界 $i$（对于 $1\le i\le N$）位于 $x$ 坐标 $i$，$y$ 坐标 $A_i$。每个世界里还有一头奶牛。在时刻 $0$，所有的 $y$ 坐标各不相同，然后这些世界开始坠落：世界 $i$ 沿着 $y$ 轴负方向以 $i$ 单位每秒的速度移动。
在任意时刻，如果两个世界在某一时刻 $y$ 坐标相同（可能是非整数时刻），传送门之间就会「同步」，使得其中一个世界的奶牛可以选择瞬间传送到另一个世界。
对于每一个 $i$，在世界 $i$ 的奶牛想要去往世界 $Q_i$。帮助每头奶牛求出如果她以最优方案移动需要多少时间。
每个询问的输出是一个分数
有 $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$ 个空格分隔的整数 $A_1,A_2,\ldots ,A_N$。
下一行包含 $N$ 个空格分隔的整数 $Q_1,Q_2,\ldots ,Q_N$。
输出格式
输出 $N$ 行，第 $i$ 行包含奶牛 $i$ 的旅程的时间。
输入输出样例
输入 #1
4 3 5 10 2 3 3 2 1
输出 #1
7/2 7/2 5/1 -1
说明/提示
对于全部测试点，$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$ 没有额外限制。
测试点 $2,3$ 满足 $N\le 100$。
测试点 $4,5$ 满足 $N\le 2\cdot 10^3$。
测试点 $6\sim 14$ 没有额外限制。