B. Хагас шигшээ

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Тэмцээний хоёр хагас шигшээ явагдаж байна. Хагас шигшээ бүрд $n$ оролцогч байгаа. Эцсийн шалгаруултанд $n$ хүн үлдэх ба дараах байдлаар сонгогдоно. Хагас шигшээ бүрээс хамгийн өндөр үзүүлэлттэй $k (0 ≤ 2k ≤ n)$ хүнийг сонгож үлдсэн хүмүүсээс хамгийн өндөр үзүүлэлттэй $n - 2k$ хүнийг сонгоно.

Тэмцээний зохион байгуулагчид одоогоор $k$-ийн утгыг шийдээгүй байгаа. Тиймээс оролцогчид хэнд нь эцсийн шатанд оролцох боломж байгааг мэдэхийг хүсчээ.

Оролт

Эхний мөрөнд хагас шигшээ бүрд оролцож байгаа оролцогчийн тоо $n (1 ≤ n ≤ 10^5)$. Дараагийн $n$ мөрөнд $a_i,\ b_i (1 ≤ a_i, b_i ≤ 10^9)$ (хагас шигшээг дуусгасан миллсекунт) бүхэл тоонууд байна. Энэ нь шигшээ бүрийн $i$-р оролцогчийн эхний ба 2-р хагас шигшээний дүн өгөгдөнө. Бүх дүн ялгаатай байна. $a_1$, $a_2$,..., $a_n$ ба $b_1$, $b_2$,..., $b_n$ дараалал өсөх эрэмбээр өгөгдөнө.

Гаралт

$0,\ 1$-ээс бүрдсэн $n$ урттай 2 тэмдэгт мөр хэвдэнэ. Эхний мөрөнд эхний хагас шигшээний оролцогчдыг, дараагийн мөрөнд 2-р хагас шигшээний оролцогчдыг илтгэнэ. $i$-р мөрийн $j$-дэх тэмдэгт нь $1$ бол $i$-р хагас шигшээн $j$-дэх оролцогч шалгарах боломжиой гэсэн үг. Үгүй бол $0$ байна.

Орчуулсан: Говьхүү

Жишээ тэстүүд

Оролт
4
9840 9920
9860 9980
9930 10020
10040 10090
Гаралт
1110
1100
Оролт
4
9900 9850
9940 9930
10000 10020
10060 10110
Гаралт
1100
1100

Тэмдэглэл

Consider the first sample. Each semifinal has 4 participants. The results of the first semifinal are 9840, 9860, 9930, 10040. The results of the second semifinal are 9920, 9980, 10020, 10090.

  • If $k = 0$, the finalists are determined by the time only, so players 9840, 9860, 9920 and 9930 advance to the finals.
  • If $k = 1$, the winners from both semifinals move to the finals (with results 9840 and 9920), and the other places are determined by the time (these places go to the sportsmen who run the distance in 9860 and 9930 milliseconds).
  • If $k = 2$, then first and second places advance from each seminfial, these are participants with results 9840, 9860, 9920 and 9980 milliseconds.
Сэтгэгдлүүдийг ачааллаж байна...