eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

G. Кольоровi книги

G. Кольоровi книги

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Сьогоднi Козак Вус знайшов поличку книг. Усього на поличцi було n книг, розташованих у ряд. На кожнiй книзi було написане одне цiле число a[i]. Усi цi числа рiзнi з промiжку [1; n]. Iншими словами, a — перестановка. Також кожна книга має свiй колiр, колiр i-ої книги c[i].

Козак хоче навести лад на поличцi, для цього потрiбно, щоб книги йшли в порядку зростання чисел, записаних на них, тобто книга 1 iде першою, наступна 2 i так далi. За одну операцiю вiн може помiняти мiсцями будь-якi двi книги рiзного кольору. Допоможiть Вусу впоратись з цiєю задачею за мiнiмальну кiлькiсть операцiй. Гарантується, що це можливо зробити.

Входные данные

Перший рядок мiстить одне цiле число n (1 ⩽ n ⩽ 10^5) — кiлькiсть книг.

Другий рядок мiстить n цiлих чисел a[1]; a[2]; : : : ; a[n] (1 ⩽ a[i] ⩽ n) — числа, записанi на книгах.

Гарантується, що всi числа рiзнi.

Третiй рядок мiстить n цiлих чисел c[1]; c[2]; : : : ; c[n] (1 ⩽ c[i] ⩽ n) — кольори книг.

Гарантується, що рiшення завжди iснує.

Выходные данные

У першому рядку виведiть одне число k — кiлькiсть операцiй.

У наступних k рядках виведiть по два цiлi числа — позицiї книг, якi потрiбно пом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х тестах з блоку.

  1. (10 балiв) 1 000 < n ⩽ 10^5, усi кольори рiзнi.

  2. (40 балiв) без додаткових обмежень.

Пример

Входные данные #1
7
2 5 3 7 1 6 4
3 2 2 3 3 2 3
Выходные данные #1
5
2 4
7 4
2 7
1 2
1 5
Входные данные #2
2
2 1
1 2
Выходные данные #2
1
1 2
Источник XXXII Всеукраїнська олiмпiада з iнформатики, Одеса, 25-29 березня 2019 року