There is a street of length L meters stretching from left to right, and N lampposts, each occupying a different position along the street and an integer number of meters from the leftmost point on the street. You want to find out the positions of all lampposts. The lampposts are numbered 0 to N-1 from left to right. It is guaranteed that lamppost 0 will be at the leftmost point on the street, and each lamppost will be an even number of meters away from the leftmost point on the street.
However, as you do not like to walk, you will send Gug to do stuff instead. For a total of at most Q times, you may send Gug to a specific position an integer number of meters from the leftmost point on the street, and Gug will tell you the ID of the lamppost that is closest to him. If there is a tie, Gug will choose the one with the smaller ID.
This is a function call problem. You are tasked to implement one function.
void find_lampposts(int L, int N, int X[])
The find_lampposts function will be called exactly once, indicating a street with L meters and N lampposts. You are to find out the positions of each individual lamppost and set X[i] to be the number of meters the i-th lamppost is from the leftmost point on the street.
You may call the following grader functions to find your answer.
int nearest_lamppost(int X)
The nearest_lamppost function will return the ID of the nearest lamppost as seen from the position X meters from the leftmost point on the street. If there is a tie, it will return the one with the smaller ID. X must be between 0 and L.
Subtask 1 (16%): L = 100000, N = 2, Q = 100001.
Subtask 2 (21%): L = 100000, N = 100, Q = 100001.
Subtask 3 (20%): L = 100000, N = 2, Q = 20.
Subtask 4 (43%): L = 100000, N = 1000, Q = 20000. See 'Scoring' for additional details.
Subtask 5 (0%): Sample Testcases.
Subtask 4 will be a special scoring subtask. The score you gain will be dependent on the number of queries you make. Let the number of maximum queries made be q.
If q ≤ 7500, you will obtain 43 marks.
If 7500 < q ≤ 20000, you will obtain 40-30*((q - 7500) / 12500) marks.
If q > 20000, you will obtain 0 marks.
The first line of input will contain three integers, L, N and Q.
The second line of input will contain N integers, with the ith integer representing the position of the lamppost with ID i.
The grader output should contain one line with N integers, with the ith integer representing the reported position of the lamppost with ID i.
The grader will also output the number of queries used.
100000 5 100001 0 22222 56124 88888 99954
| Subtask | Score |
|---|---|
| 1 | 16 |
| 2 | 21 |
| 3 | 20 |
| 4 | 43 |
| 5 | 0 |