問題一覧 > 通常問題

No.953 席

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

問題文

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

雪屋には入口が 1 つだけあり、入口から最も近い席は席 K1 です。
入口から 2 番目に近い席は席 K2(だけ)です(席 K2 は席 K1 の隣の席です)。

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

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

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

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

入力

N K1 K2
Q
a1 b1
a2 b2

aQ bQ

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

  • 2N105
  • 1K1,K2N
  • |K1K2|=1
  • 1Q105
  • 1a1<a2<<aQ109
  • 1bi109 (1iQ)

出力

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