Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |

Задачи на идею

Олимпиадные задачи на английском языке

Олимпиадные задачи на английском языке

25/06/2012 | Лето 2012 - дорешивание (12G) |

12/07/2012 | Лето 2012 - 12 (командный) (G) |

*Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

In Mirko’s village all fences are made of exactly `N` boards with different heights. Mirko doesn’t have
his own fence yet, so he decided to build one.

Each board is represented by a positive integer less than 10^9 – it’s height. We define the *niceness* of the
fence as a sum of height differences between adjacent boards.

Mirko already bought the boards, but he doesn’t know how to order them into a fence. He would like
his fence to be similar to Slavko’s fence, but also to be as nice as possible.

We say that two fences are *similar* if ordering of adjacent boards is the same in both fences, i.e. if `i`-th
board of one fence is smaller (or larger) than `(i+1)`-st, than the same must hold for that boards of the
other fence.

Given Slavko’s fence configuration, and heights of boards that Mirko bought, put Mirko’s fence
together so that it is similar to Slavko’s but also as nice as possible. If there is more than one solution,
output any of them.

The first line of input contains integer `N` (`2\ ≤\ N\ ≤\ 300\ 000`), number of boards in each fence.

The following line contains `N` different positive integers representing Slavko’s fence.

The following line contains `N` different positive integers representing heights of boards Mirko bought
for his fence.

The first line of output should contain the maximum possible niceness of Mirko’s fence.

The following line should contain `N` integers, Mirko’s boards in optimal order as described.

Sample Input #1

4 5 7 4 9 1 2 3 4

Sample Output #1

7 2 4 1 3

Sample Input #2

10 9 5 1 2 6 7 4 18 20 12 10 40 20 30 50 70 80 100 1000 500

Sample Output #2

3010 100 80 10 40 50 1000 20 70 500 30