問題一覧 > 通常問題

No.953 Seats

レベル : / AI推定難易度 : 1625 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 34
作問者 : %20 / テスター : kotatsugame
お気に入りにしたユーザー ProblemId : 2386 / 自分の提出
問題文最終更新日: 2019-12-15 18:14:24
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2019 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。