Офісна Вулиця. Частина 2
Обмеження: 2 сек., 256 МіБ
Зустрілися якось працівники великих компаній і почали... обговорювати план вулиці.
Виявляється, всі приміщення, які орендуватимуть ці компанії, збудують уздовж однієї вулиці.
\(i\)-та компанія орендуватиме офіс довжиною \(l_i\) метрів, і в цьому офісі працюватимуть \(w_i\) працівників. Офіси будуватимуть один за одним, починаючи з точки 0. Працівники всіх компаній приїжджатимуть на автобусну зупинку в точці 0 та будуть іти до офісів своїх компаній.
Тобто, якщо офіси будуть збудовані в порядку \(p_1, p_2, \dots, p_n\), то перший офіс почнеться в точці 0 і закінчиться в точці \(l_{p_1}\), другий почнеться в \(l_{p_1}\) і закінчиться в \(l_{p_1} + l_{p_2}\) і т.д. Двері кожного офісу завжди є в кінці будинку, який є ближчим до стоянки.
Ваше завдання — допомогти розмістити офіси компаній на цій вулиці в такому порядку, щоб сума відстаней, яку повинні пройти всі працівники до своїх офісів, була мінімальною.
Вхідні дані
У першому рядку задане ціле число \(n\) — кількість компаній.
У другому рядку задано \(n\) цілих чисел \(l_i\) через пробіл — довжини офісів усіх компаній.
У наступному рядку задано \(n\) цілих чисел \(w_i\) через пробіл — кількість працівників, що працюють в офісі \(i\)-ї компанії.
Вихідні дані
У єдиному рядку виведіть \(n\) чисел від 1 до \(n\) — порядок компаній, у якому варто будувати офіси.
Якщо існує декілька оптимальних порядків — виведіть будь-який із них.
Обмеження
\(1 \le n \le 10^5\),
\(1 \le l_i \le 10^4\),
\(1 \le w_i \le 10^4\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
4 4 1 2 3 7 1 4 2 | 3 1 2 4 |
Примітки
Якщо розставити компанії в порядку 3, 1, 2, 4, то:
відстань до офісу першої компанії — 2,
відстань до офісу другої компанії — 6,
до офісу третьої компанії — 0,
до офісу четвертої компанії — 7,
сума відстаней — \(2 \cdot 7+6 \cdot 1+0 \cdot 4+7 \cdot 2=34\).
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|