Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
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.