Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
D. Миша ба сэлгэмлүүдийн нийлбэр
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
$0, 1, ..., (n - 1)$ тоонуудаар үүсэх сэлгэмэлүүдийн толь бичгийн дарааллын дагуу $x$ дэх сэлгэмлийг ($0$-ээс эхлэн дугаарлана) $Perm(x)$ гэе. Харин $Ord(p)$ нь $p$ сэлгэмлийн толь бичгийн эрэмбээрх дугаар нь байг. $0, 1, ..., (n - 1)$ тоонуудаар үүсэх $p$ болон $q$ сэлгэмлүүдийн нийлбэр гэдгээр $Perm(Ord(p) + Ord(q))\ mod\ n!)$ сэлгэмэлийг тодорхойлъё.
Жишээ нь: $Perm(0) = (0, 1, ..., n-2, n-1)$; $Perm(n!-1) = (n-1, n-2, ..., 1, 0)$
Мишад $p$ ба $q$ гэсэн хоёр сэлгэмэл байгаа. Чиний даалгавар бол тэдгээрийн нийлбэрийг олох юм.
Хэрэв $a_{0} = b_{0}, a_{1} = b_{1}, ..., a_{k - 1} = b_{k - 1}, a_{k} < b_{k}$ нөхцлийг хангадаг байхаар $k$ дугаар олддог бол сэлгэмэл $a = (a_{0}, a_{1}, ..., a_{n - 1})$-г сэлгэмэл $b = (b_{0}, b_{1}, ..., b_{n - 1})$-ээс толь бичгийн эрэмбээрээ бага гэж үзнэ.
Оролт
Эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 200000$) байрлана.
Хоёр дахь мөрөнд $p$ сэлгэмлийг илэрхийлсэн $0$-ээс $n-1$ хүртэлх ялгаатай $n$ ширхэг бүхэл тоо зайгаар тусгаарлагдан байрлана.
Гурав дахь мөрөнд $q$ сэлгэмлийг илэрхийлсэн $0$-ээс $n-1$ хүртэлх ялгаатай $n$ ширхэг бүхэл тоо зайгаар тусгаарлагдан байрлана.
Гаралт
Өгөгдсөн сэлгэмлүүдийн нийлбэр сэлгэмлийг илэрхийлсэн $0$-ээс $n-1$ хүртэлх ялгаатай $n$ ширхэг бүхэл тоог зайгаар тусгаарлан хэвлэ.
Орчуулсан: Бат-Од
Жишээ тэстүүд
Оролт
2 0 1 0 1
Гаралт
0 1
Оролт
2 0 1 1 0
Гаралт
1 0
Оролт
3 1 2 0 2 1 0
Гаралт
1 0 2
Тэмдэглэл
$0$-ээс $1$ хүртэлх тоонуудаар үүсэх сэлгэмэлүүдийн толь бичгийн эрэмбэ нь: $(0, 1), (1, 0)$.
Эхний жишээнд $Ord(p) = 0$ ба $Ord(q) = 0$ тул хариу:
$Perm((0+0)\ mod\ 2) = Perm(0) = (0, 1)$.
Хоёр дахь жишээнд $Ord(p) = 0$ ба $Ord(q) = 1$ тул хариу:
$Perm((0+1)\ mod \ 2) = Perm(1) = (1, 0)$.
$0$-ээс $2$ хүртэлх тоонуудаар үүсэх сэлгэмлүүдийн толь бичгийн эрэмбэ нь: $(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)$.
Гурав дахь жишээнд $Ord(p) = 3$ ба $Ord(q) = 5$ тул хариу:
$Perm((3 + 5)\ mod\ 6) = Perm(2) = (1, 0, 2)$.