No.953 Seats
タグ : / 解いたユーザー数 34
作問者 :
%20
/ テスター :
Problem Statement
The restaurant "Yukiya" has $N$ seats, arranged in a straight line at equal intervals.
The seats are numbered from $1$ to $N$ in order from one end.
Yukiya has only $1$ entrance, and the seat closest to the entrance is seat $K_1$.
The $2$-nd closest seat to the entrance is seat $K_2$ (and only that seat) (seat $K_2$ is adjacent to seat $K_1$).
Every customer who comes to Yukiya takes a seat according to the following conditions (if there is a vacant seat, they sit immediately).
- If there are vacant seats where the customer can sit without being adjacent to another customer, they sit in the one closest to the entrance among such seats.
- If there is no vacant seat where the customer can sit without being adjacent to another customer, they sit in the vacant seat closest to the entrance.
- If there are no vacant seats, they wait until a seat becomes vacant, and then take a seat according to the conditions above.
$Q$ customers came to Yukiya.
The $i$-th customer arrived at time $a_i$, and the time from sitting down to leaving the seat was $b_i$.
Determine which seat each customer sat in.
Note that all seats were vacant at time $0$, and customers take seats in order of arrival.
Also note that if a customer $y$ leaves their seat at the same moment a customer $x$ arrives, the seat customer $y$ was sitting in is regarded as vacant by customer $x$.
Input
$N$ $K_1$ $K_2$ $Q$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_Q$ $b_Q$
All inputs are integers and satisfy the following constraints.
- $2 \le N \le 10^5$
- $1 \le K_1,K_2 \le N$
- $|K_1-K_2|=1$
- $1 \le Q \le 10^5$
- $1 \le a_1 \lt a_2 \lt \dots \lt a_Q \le 10^9$
- $1 \le b_i \le 10^9\ (1 \le i \le Q)$
Output
Output $Q$ lines.
On the $i$-th line, output the number of the seat in which the $i$-th customer sat.
Sample
Sample 1
Input
5 3 4 7 1 49 2 48 3 47 5 40 8 42 13 100 21 100
Output
3 5 1 4 2 4 2
The positions of the seats relative to the entrance are as shown in the figure below.
Listing the seat numbers in order of proximity to the entrance gives $3(=K_1),4(=K_2),2,5,1$.
At time $1$, all seats are vacant. Customer $1$ sits in seat $3$, the seat closest to the entrance.
At time $2$, the seats not adjacent to customer $1$ are seats $5,1$. Of seats $5$ and $1$, seat $5$ is closer to the entrance, so customer $2$ sits in seat $5$.
At time $3$, the only seat not adjacent to customers $1,2$ is seat $1$. Therefore, customer $3$ sits in seat $1$.
At time $5$, there is no seat that is not adjacent to customers $1,2,3$, and the vacant seats are seats $4,2$. Of seats $4$ and $2$, seat $4$ is closer to the entrance, so customer $4$ sits in seat $4$.
At time $8$, the only vacant seat is seat $2$. Therefore, customer $5$ sits in seat $2$.
At time $13$, there are no vacant seats. Customer $6$ waits until a seat becomes vacant.
At time $21$, there are no vacant seats. Customer $7$ waits until a seat becomes vacant.
At time $45$, seat $4$, where customer $4$ was sitting, becomes vacant, so customer $6$ sits in seat $4$.
At time $50$, seats $3,5,1,2$, where customers $1,2,3,5$ were sitting, become vacant, so customer $7$ sits in seat $2$, which is not adjacent to customer $6$.
This can be illustrated as follows.
K_1 K_2
1 2 3 4 5
0 [ ] [ ] [ ] [ ] [ ]
1 [ ] [ ] [1] [ ] [ ]
2 [ ] [ ] [1] [ ] [2]
3 [3] [ ] [1] [ ] [2]
5 [3] [ ] [1] [4] [2]
8 [3] [5] [1] [4] [2]
13 [3] [5] [1] [4] [2] 6
21 [3] [5] [1] [4] [2] 6 7
45 [3] [5] [1] [6] [2] 7
50 [ ] [7] [ ] [6] [ ]
Sample 2
Input
10 5 6 20 1 15 5 117 10 60 27 11 35 43 38 16 41 97 50 124 61 106 82 70 86 79 92 144 96 71 108 17 126 27 127 18 131 5 133 119 181 38 192 4
Output
5 7 3 5 9 5 1 6 5 3 9 4 8 2 7 2 10 10 6 8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。