Way: Ad Hoc

Query complexity: ~3(N-1)~

Time complexity: ~\mathcal O(N \log N)~

** This problem can be solved by the following steps:

First, we know that station ~0~ is C type, and its location. We can query all the other stations' distances from station ~0~, we call this: ~dis[0][i]~

Second, we sort all the ~dis[0][i]~, and obviously, the station ~x~ with the shortest distance ~dis[0][x]~ must be the first D type location after station ~0~.

Third, we process each station one by one according to their shortest distance with station ~0~ (that is, the order obtained in second step). For each station processed, we determine its type and location immediately as follows:

3.1 First, we maintain the information (location,id) of the leftmost C type and the rightmost D type as the algorithm proceeds.

3.2 To process the current station ~k~, we use two queries, query(k,leftmost C type) as ~dis[k][L]~, query(k, rightmost D type) as ~dis[k][R]~. And we also have ~dis[0][k]~. By some observations, we know that either ~dis[k][L]~ or ~dis[k][R]~ is achieved with a 'direct' route (without moving forth and back).

For example, we have only 4 cases to consider:

a. dis[k][L] is a direct route
       (   )   )
       L   k   R

b. dis[k][L] is a direct route
       (       )    )
       L       R    k

c. dis[k][R] is a direct route
    (  (       )
    k  L       R

d. dis[k][R] is a direct route
       (   (   )
       L   k   R

By careful analysis (some if/else conditions), we can get the answer. Sometimes, we may need extra information to resolve the four cases, where we can check with ~dis[0][k]~.

Take case (a) for example:

a. dis[k][L] is a direct route
       (   )   )
       L   k   R

the location of ~k~ might be ~L+dis[k][L]~. Then use this location, we need to check if ~dis[k][R]~ is reasonable or not.

a.1
       ( ( )   )
       L p k   R

There might be some ~p~ (type C) between ~L~ and ~k~. So ~dis[k][R]~ is ~dis[p][R]+dis[p][k]~, we need to check whether ~p~ exists or not. If ~p~ doesn't exist, then case (a) might be wrong, then try cases (b), (c), and (d) until we find the answer.