CodeChef: June Challenge | Shortest Route | Full Solution
There are NN cities in Chefland numbered from 11 to NN and every city has a railway station. Some cities have a train and each city has at most one train originating from it. The trains are represented by an array AA, where Ai=0Ai=0 means the ii-th city doesn’t have any train originating from it, Ai=1Ai=1 means the train originating from the ii-th city is moving right (to a higher numbered city), and Ai=2Ai=2 means the train originating from the ii-th city is moving left (to a lower numbered city).
Each train keeps on going forever in its direction and takes 11 minute to travel from the current station to the next one. There is a special station at city 11 which lets travellers instantaneously teleport to any other station that currently has a train. Teleportation and getting on a train once in the city both take 00 minutes and all trains start at time 00.
There are MM travellers at city 11, and the ii-th traveller has destination city BiBi. They ask Chef to guide them to teleport to a particular station from which they can catch a train to go to their destination in the least time possible. In case it’s not possible for a person to reach his destination, print −1−1.
Note: The input and output of this problem are large, so prefer using fast input/output methods.
Input
- The first line contains an integer TT, the number of test cases. Then the test cases follow.
- Each test case contains three lines of input.
- The first line contains two integers NN, MM.
- The second line contains NN integers A1,A2,…,ANA1,A2,…,AN.
- The third line contains MM integers B1,B2,…,BMB1,B2,…,BM.
Output
For each test case, output MM space-separated integers C1,C2,…,CMC1,C2,…,CM, where CiCi is the minimum time required by the ii-th traveller to reach his destination and if the ii-th traveller can’t reach his destination, Ci=−1Ci=−1.
Constraints
- 1≤N,M≤1051≤N,M≤105
- 0≤Ai≤20≤Ai≤2
- 1≤Bi≤N1≤Bi≤N
- The sum of NN over all test cases is at most 106106.
- The sum of MM over all test cases is at most 106106.
Subtasks
Subtask #1 (100 points): original constraints
Sample Input
3
5 1
1 0 0 0 0
5
5 1
1 0 0 0 2
4
5 2
2 0 0 0 1
3 1
Sample Output
4
1
-1 0
Explanation
Test Case 1: The only person takes the train from station 11 and hence takes |5−1|=4|5−1|=4 minutes to reach his destination.
Test Case 2: The only person takes the train from station 55 and hence takes |5−4|=1|5−4|=1 minute to reach his destination.
Test Case 3: Since no train passes station 33, it’s impossible for the first person to reach his destination and since the second person is already at station 11, it takes him 00 minutes to reach his destination.
Solution
Due to copyright issues we won’t be able to update the solution here immediately. However you can download the code file from our telegram channel. So join our telegram channel for further updates. Keep tracking, the solution will be updated on this website soon.
Read more post Here
