OGLEDALA, 100 points
레이팅 미적용의견: 0
CROATIAN OLYMPIAD IN INFORMATICS 2015
Time limit: 4 seconds
Memory limit: 512 MB
Page \(1/2\)
There are \(M\) modern washbasins numbered from 1 to \(M\) from left to right in the ladies’ room of an enormous
shopping centre.
Currently, there are \(N\) ladies in the restroom (numbered from 1 to \(N\)) and they’ve occupied the washbasins
with numbers \(A\)1, A2, . . . , A_{N}. Soon there will be \(M - N\) more ladies arriving (numbered from \(N + 1\) to \(M\)
in the order of arrival) that will occupy all the remaining available washbasins. The ladies arriving primarily
want their privacy, so each of them always chooses an available washbasin by the following procedure:
• First she finds the largest consecutive series of available washbasins. If there is more than one, she
chooses the leftmost.
• After that, she occupies the middle washbasin in the chosen series. If the series is of even length, she
chooses the left of the two middle washbasins.
It is safe to assume that none of the ladies will leave the washbasin in the foreseeable future.
Write a programme that will, for each of \(Q\) given integers \(B@@RISE_MATH_BLOCK_0@@i\).
subtask
subscore
constraints
1
19
1 ⩽\(M\) ⩽300 000
2
22
1 ⩽\(M\) ⩽\(10^{14}\), \(B_{Q}\) ⩽300 000
3
59
1 ⩽\(M\) ⩽\(10^{14}\)
In all subtasks, it will hold 1 ⩽\(Q\) ⩽\(10^{5}\), \(N\) ⩽\(M\) and 1 ⩽\(N\) ⩽\(10^{5}\).
The first line of input contains integers \(M\), \(N\) and \(Q\) – the number of washbasins, the initial number of ladies
in the restroom and the number of ladies for which you need to determine which washbasin they will use.
The second line of input contains \(N\) spa\(ce-se\)parated integers, the \(i\)^{th} of those numbers is \(A_{i}\) – the label of
the washbasin that is being used by lady \(i\).
The third line of input contains \(Q\) spa\(ce-se\)parated integers, the \(i\)^{th} of those numbers is \(B_{i}\) – the label of the
lady for which we want to know which washbasin she will use.
The first \(N\) ladies in the restroom haven’t necessarily chosen their washbasins using the procedure described
in the task.
The arrays \(A\) and \(B\) are strictly increasing. In other words, it holds 1 ⩽\(A_{1} < A_{2}\) < . . . < \(A_{N}\) ⩽\(M\) and
1 ⩽\(B\)\(1 < B\)2 < . . . < B_{Q} ⩽\(M\).
Output \(Q\) lines. The \(i\)^{th} line must contain the label of the washbasin that will be used by the lady labeled
\(B_{i}\).
Please note: We recommend that you use a \(64-bi\)t integer data type (int64 in Pascal, long long in
\(C/C\)++).
CROATIAN OLYMPIAD IN INFORMATICS 2015
Time limit: 4 seconds
Memory limit: 512 MB
Page \(2/2\)
7 1 4
4
2 3 4 5
10 2 4
2 8
1 3 5 8output
2
6
1
3
2
5
6
4Clarification of the second example: The first two ladies occupy the washbasins 2 and 8 (respectively).
The remaining ladies occupy the washbasins 5, 3, 6, 9, 1, 4, 7 and 10, respectively.
평가 및 의견
OGLEDALA, 100 points
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
OGLEDALA, 100 points