077 - Planes on a 2D Plane(★7) Editorial /

Time Limit: 1.5 sec / Memory Limit: 1024 MB

配点: 7

問題文

2 次元座標平面とみなせる大空に、N 機の飛行機が航行しています。
i=1,2, \cdots ,N に対し、 i 番目の飛行機は時刻 0 において座標 (AX_i,AY_i) に存在しました。

飛行機はいずれも向き 1,2,3,4,5,6,7,8 のいずれかを向いて航行しています。
時刻 t において座標 (x,y) に存在する向き d の飛行機は、 時刻 t+1 において

  • d=1 ならば座標 (x+1,y)
  • d=2 ならば座標 (x+1,y+1)
  • d=3 ならば座標 (x,y+1)
  • d=4 ならば座標 (x-1,y+1)
  • d=5 ならば座標 (x-1,y)
  • d=6 ならば座標 (x-1,y-1)
  • d=7 ならば座標 (x,y-1)
  • d=8 ならば座標 (x+1,y-1)

存在します。
また、航行の途中で飛行機が向きを変えることはありません。

あなたは管制官の高橋くんから次のような報告を受けました。

時刻 T において、座標 (BX_1,BY_1),(BX_2,BY_2), \cdots ,(BX_N,BY_N) に飛行機が存在した

彼の報告に矛盾しないような N 機の飛行機の向きの組み合わせが存在するかを判定し、存在する場合は一例を出力してください。

制約

  • 1 \leq N \leq 20000
  • 1 \leq T \leq 10^9
  • 0 \leq AX_i,AY_i,BX_i,BY_i \leq 10^9
  • i \ne j ならば (AX_i,AY_i) \ne (AX_j,AY_j)
  • i \ne j ならば (BX_i,BY_i) \ne (BX_j,BY_j)
  • 入力はすべて整数

小課題・得点

この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。

  1. (1 点):N \leq 6
  2. (1 点):AY_i=0, BY_i=0
  3. (2 点):N \leq 1000
  4. (3 点):追加の制約はない。

入力

入力は以下の形式で標準入力から与えられます。

N T
AX_1 AY_1
AX_2 AY_2
 \vdots 
AX_N AY_N
BX_1 BY_1
BX_2 BY_2
 \vdots 
BX_N BY_N

出力

高橋くんの報告に矛盾しない向きの組み合わせが存在しない場合、No と出力してください。
存在する場合、以下の形式で 1, 2, \cdots, N 番目の飛行機の向きを空白区切りで出力してください。ただし、D_i は飛行機 i の向きとします。

Yes
D_1 D_2 D_3 \cdots D_N

入力例 1

3 2
3 3
5 5
9 2
11 2
5 5
3 3

出力例 1

Yes
2 6 1

時刻 T において、1 番目の飛行機は座標 (BX_2,BY_2) に、2 番目の飛行機は座標 (BX_3,BY_3) に、3 番目の飛行機は座標 (BX_1,BY_1) に存在します。


入力例 2

3 2
3 3
5 5
9 2
11 1000000000
5 5
3 3

出力例 2

No

高橋くんの報告に矛盾しない向きの組み合わせは存在しません。


入力例 3

20 774
540130346 269080121
139837096 165633078
731188937 784167460
18996195 52176517
153153670 738204723
179733158 825294112
698198250 713974773
449248931 563096572
249863070 242694893
428066819 476630383
554127636 460973490
389988495 32320086
889782910 956212985
43905938 212030305
638141790 667879166
985957895 358743012
971007109 827787244
804625543 141347414
905270323 167192824
614855582 963943648
179733932 825294886
731188163 784166686
153154444 738205497
554128410 460973490
804626317 141348188
449249705 563096572
540129572 269079347
638142564 667878392
614855582 963944422
18996969 52177291
971007109 827788018
889782910 956213759
43906712 212031079
389987721 32319312
139836322 165633078
428067593 476631157
905271097 167192824
249862296 242694893
985958669 358742238
698199024 713975547

出力例 3

Yes
6 5 6 2 2 2 2 1 5 2 1 6 3 2 8 8 3 2 1 3

Source Name

「競プロ典型90問」77日目