G. Кольоровi книги
G. Кольоровi книги
Сьогодні Козак Вус знайшов поличку книг. Усього на поличці було n книг, розташованих у ряд. На кожній книзі було написане одне ціле число ai
. Усi цi числа рiзнi з проміжку [1; n]. Іншими словами, a — перестановка. Також кожна книга має свiй колiр, колiр i-ої книги ci
.
Козак хоче навести лад на поличці, для цього потрібно, щоб книги йшли в порядку зростання чисел, записаних на них, тобто книга 1 iде першою, наступна 2 i так далi. За одну операцію вiн може поміняти місцями будь-якi дві книги різного кольору. Допоможіть Вусу впоратись з цiєю задачею за мінімальну кількість операцій. Гарантується, що це можливо зробити.
Формат вхідних даних:
Перший рядок містить одне ціле число n (1 ≤ n ≤ 105
) — кількість книг.
Другий рядок містить n цiлих чисел a1
; a2
; : : : ; an
(1 ≤ ai
≤ n) — числа, записанi на книгах.
Гарантується, що всi числа рiзнi.
Третiй рядок містить n цiлих чисел c1
; c2
; : : : ; cn
(1 ≤ ci
≤ n) — кольори книг.
Гарантується, що рішення завжди iснує.
Формат вихідних даних:
У першому рядку виведіть одне число k — кількість операцій.
У наступних k рядках виведіть по два цiлi числа — позиції книг, якi потрібно поміняти місцями.
Оцінювання:
1) (до 50 балiв) n ≤ 1 000; припустимо, що m — мiнiмальна кiлькiсть операцiй, якi потрiбно зробити, щоб вiдсортувати книги в певному тестi, а k — кiлькiсть операцiй, якi ви використали. Тодi результат за цей тест буде рiвний:
50, якщо k = m
10 + ⌊30 - 30 * (k - m)/(3n - m)⌋, якщо m < k ⩽ 3n
0, якщо k > 3n.
Ваша кiлькiсть балiв за цей блок буде рiвною мiнiмуму з результатiв у всiх тестах з блоку.
2) (10 балiв) 1 000 < n ⩽ 105
, усi кольори рiзнi.
3) (40 балiв) без додаткових обмежень.
7 2 5 3 7 1 6 4 3 2 2 3 3 2 3
5 2 4 7 4 2 7 1 2 1 5
2 2 1 1 2
1 1 2