P6607 [Code+#7] Ants

A thin rope of length $L$ is hung between two trees arranged from east to west. There are $N$ ants on the rope. These ants want to crawl along the rope to reach either tree, but the rope is so thin that two ants cannot crawl side by side, nor can they pass through each other. They come up with a method: each ant keeps moving forward at a speed of 1 unit distance per unit time. When two ants meet head-on, both ants immediately turn around and continue moving forward. Now, the ants want to know whether they can crawl off the rope. If they can, they also want to know how long it takes for each of them to crawl off. For convenience, we number the ants starting from $1$ in the order of their initial positions from east to west.

The first line contains two positive integers $N, L$, with $N \le 10^5$, $L \le 10^9$, and $N < L$. The second line contains $N$ positive integers. The $i$-th number $p_i$ denotes the distance from the $i$-th ant to the eastern tree. It is guaranteed that $p_i$ is strictly increasing as $i$ increases, and $0 < p_i < L$. The third line contains $N$ integers. For the $i$-th number $d_i$, if it is $1$, it means the $i$-th ant initially faces west; if it is $0$, it means it initially faces east.

Output a single line containing $N$ numbers. The $i$-th number denotes the time it takes for the $i$-th ant to crawl off the rope, rounded to the nearest integer. If the $i$-th ant cannot crawl off the rope, output $-1$ for the $i$-th number.

### Sample Explanation The third ant meets the second ant after crawling for 1 unit of time and turns around, then crawls for 2 more units of time to reach the western tree. The second ant meets the third ant after crawling for 1 unit of time and turns around, then meets the first ant after crawling for 1 more unit of time and turns around, then crawls for 3 more units of time to reach the western tree. The first ant meets the second ant after crawling for 2 units of time and turns around, then crawls for 3 more units of time to reach the eastern tree. ### Subtasks Subtask 1 (17 points) - $1 \le N \le 10, L \le 10^5$. Subtask 2 (19 points) - $1 \le N \le 100, L \le 10^9$. Subtask 3 (27 points) - $1 \le N \le 5000, L \le 10^9$. Subtask 4 (37 points) - $1 \le N \le 10^5, L \le 10^9$. Translated by ChatGPT 5