問題一覧 > 通常問題

No.953 席

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 31
作問者 : %20%20 / テスター : kotatsugamekotatsugame
2 ProblemId : 2386 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-12-15 18:14:24

問題文

飲食店「雪屋」には、$N$ 脚の席があり、それらは一直線上に等間隔に並んでいます。
各席には端から順に $1$ から $N$ までの番号がついています。

雪屋には入口が $1$ つだけあり、入口から最も近い席は席 $K_1$ です。
入口から $2$ 番目に近い席は席 $K_2$（だけ）です（席 $K_2$ は席 $K_1$ の隣の席です）。

雪屋に来るすべての客は、次に示す条件に従って席に座ります（空席がある場合はすぐに座ります）。

  • 他の客と隣り合わないように座れる空席があれば、そのような席のうち、入口から最も近い席に座る。
  • 他の客と隣り合わないように座れる空席が無ければ、空席のうち、入口から最も近い席に座る。
  • 空席が無ければ、空席ができるまで待機した後、上記の条件に従って席に座る。

雪屋に $Q$ 人の客が来店しました。
$i$ 人目の客の来店時刻は $a_i$ で、席に座ってから席を立つまでの時間は $b_i$ でした。
各客がどの席に座ったかを答えてください。

なお、時刻 $0$ において、すべての席は空席だったものとし、客は来店順に席に座るものとします。
また、客 $x$ が来店するのと同時に席を立つ客 $y$ がいる場合、客 $y$ が座っていた席は客 $x$ からは空席とみなされることに注意してください。

入力

$N$ $K_1$ $K_2$
$Q$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_Q$ $b_Q$

入力はすべて整数で、以下の制約を満たします。

  • $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)$

出力

$Q$ 行出力してください。
$i$ 行目には $i$ 人目の客が座った席の番号を出力してください。

サンプル

サンプル1
入力
5 3 4
7
1 49
2 48
3 47
5 40
8 42
13 100
21 100
出力
3
5
1
4
2
4
2

席と入口の位置関係は下図のようになっています。

入口から近い順に席の番号を列挙すると $3(=K_1),4(=K_2),2,5,1$ です。
時刻 $1$ において、すべての席は空席です。客 $1$ は入口から最も近い席である席 $3$ に座ります。
時刻 $2$ において、客 $1$ と隣り合わないような席は席 $5,1$ です。席 $5$ と席 $1$ では席 $5$ の方が入口から近いので、客 $2$ は席 $5$ に座ります。
時刻 $3$ において、客 $1,2$ と隣り合わないような席は席 $1$ のみです。そのため、客 $3$ は席 $1$ に座ります。
時刻 $5$ において、客 $1,2,3$ と隣り合わないような席は無く、空席は席 $4,2$ です。席 $4$ と席 $2$ では席 $4$ の方が入口から近いので、客 $4$ は席 $4$ に座ります。
時刻 $8$ において、空席は席 $2$ のみです。そのため、客 $5$ は席 $2$ に座ります。
時刻 $13$ において、空席はありません。客 $6$ は空席ができるまで待機します。
時刻 $21$ において、空席はありません。客 $7$ は空席ができるまで待機します。
時刻 $45$ において、客 $4$ が座っていた席 $4$ が空席になったので、客 $6$ は席 $4$ に座ります。
時刻 $50$ において、客 $1,2,3,5$ が座っていた席 $3,5,1,2$ が空席になったので、客 $7$ は客 $6$ と隣り合わない席 $2$ に座ります。

図で表すと次のようになります。 

           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] [ ]
サンプル2
入力
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
出力
5
7
3
5
9
5
1
6
5
3
9
4
8
2
7
2
10
10
6
8

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。