Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Сплетня

(Время: 2 сек. Память: 64 Мб Сложность: 57%)

Опишем процесс распространения сплетни в коллективе из n человек. Зададим последовательность различных чисел p1, p2, …,pn – порядок, в котором люди узнают о сплетне. Человек с номером p1 является инициатором сплетни, а остальные узнают о ней от предыдущего, то есть pi узнаёт от pi−1 для 2 ≤ i.

Есть сплетня, которую нужно распространить особым образом. Дана последовательность различных номеров людей s1, s2, …, sm, где 2 ≤ m. Она означает следующее:

  • человек s1 – инициатор сплетни;
  • для каждого 2 ≤ i ≤ m человек si должен узнать о сплетне позже, чем si−1;
  • человек sm должен узнать о сплетне последним среди всех n человек.

    Для каждого человека определено целое число ai. Эти величины означают, что если человек i хочет рассказать сплетню человеку j, то на это уйдёт |ai − aj| минут.

    Определите порядок pi, который удовлетворяет требованиям выше и при котором потратится наименьшее количество времени, чтобы о сплетне узнали все n человек.

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

    Первая строка входного файла INPUT.TXT содержит целое число t – количество наборов входных данных (1 ≤ t ≤ 30 000).

    Каждый набор состоит из трёх строк. В первой строке записаны два целых числа n и m (2 ≤ m ≤ n ≤ 300 000).

    Вторая строка содержит n целых чисел a1, a2, …, an (1 ≤ ai ≤ 109).

    В третьей строке содержатся m различных целых чисел s1, s2, …, sm (1 ≤ si ≤ n).

    Гарантируется, что сумма n по всем наборам не превосходит 300 000.

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

    Для каждого тестового набора в выходной файл OUTPUT.TXT выведите n чисел в отдельной строке – оптимальный порядок распространения сплетни. Разрешается выводить любой подходящий вариант.

    Пример

    INPUT.TXTOUTPUT.TXT
    13
    5 3
    1 2 3 4 5
    3 2 5
    5 2
    10 10 10 10 10
    4 1
    8 3
    83 90 3 11 81 43 87 58
    3 1 8
    3 1 2 4 5
    4 3 5 2 1
    3 4 6 1 7 2 5 8

    Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

    [Обсуждение] [Все попытки] [Лучшие попытки]


     Язык программирования C++
     Решение олимпиадных задач
     Региональные олимпиады
     Книги Фёдора Меньшикова
     ЕГЭ по информатике
     Тренировочные олимпиады
     Личные олимпиады
     Командные олимпиады
     Первая командная олимпиада
     Вторая командная олимпиада
     Третья командная олимпиада
     Четвертая командная олимпиада
     Пятая командная олимпиада
     Шестая командная олимпиада
     A. Забытая цифра
     B. Число + олсич
     C. Соревнование кузнечиков
     D. Два квадрата
     E. Горы мусора
     F. Урок физкультуры
     G. Игра в монетку
     H. Снеговик
     I. Сплетня
     J. Кластеры

    Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru