VK Cup 2018 - Раунд 3 |
---|
Закончено |
В распоряжении одного отдела одной софтверной компании есть $$$n$$$ серверов разной мощности. Пронумеруем сервера целыми числами от $$$1$$$ до $$$n$$$. Будем считать, что технические характеристики $$$j$$$-го сервера в компании полностью определяются целочисленным количеством $$$c_j$$$ условных единиц ресурса.
Для решения текущих рабочих задач необходимо развернуть на данных серверах два сервиса — $$$S_1$$$ и $$$S_2$$$, которые будут обрабатывать входящие запросы. Обработка входящих запросов сервиса $$$S_i$$$ требует $$$x_i$$$ единиц ресурса сервера.
Действие происходит в довольно продвинутой компании, поэтому каждый сервис может быть развёрнут не на одном сервере, а одновременно на нескольких. Если сервис $$$S_i$$$ развёрнут на $$$k_i$$$ серверах, то нагрузка равномерно распределяется между этими серверами, и на каждом сервере используется только $$$x_i / k_i$$$ (возможно, нецелое число) единиц ресурса.
Каждый сервер в компании может быть либо не быть использован вообще, либо под какой-то один из сервисов (но не под оба одновременно). Сервис не должен использовать больше ресурсов, чем доступно на сервере.
Определите, возможно ли развернуть оба сервиса, используя данный набор серверов, и если да, то определите, какие серверы следует отвести под какой сервис.
В первой строке входных данных находятся три целых числа $$$n$$$, $$$x_1$$$, $$$x_2$$$ ($$$2 \leq n \leq 300\,000$$$, $$$1 \leq x_1, x_2 \leq 10^9$$$) — количество серверов в распоряжении у отдела и требуемое количество ресурсов, необходимое для каждого из сервисов.
Во второй строке находятся $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_i \leq 10^9$$$), разделённых пробелами — мощности серверов.
Если развернуть оба сервиса на данном наборе серверов невозможно, выведите единственное слово «No» (без кавычек).
В противном случае в первой строке выведите слово «Yes» (без кавычек).
Во второй строке выведите два целых числа $$$k_1$$$ и $$$k_2$$$ ($$$1 \leq k_1, k_2 \leq n$$$) — количества серверов, отведённых под каждый из сервисов.
В третьей строке выведите $$$k_1$$$ целых чисел — номера серверов, которые следует отвести под первый сервис.
В четвёртой строке выведите $$$k_2$$$ целых чисел — номера серверов, которые следует отвести под второй сервис.
Ни один номер сервера не должен встречаться среди выведенных вами номеров дважды. Если возможных ответов несколько, разрешается вывести любой из них.
6 8 16
3 5 2 9 8 7
Yes
3 2
1 2 6
5 4
4 20 32
21 11 11 12
Yes
1 3
1
2 3 4
4 11 32
5 5 16 16
No
5 12 20
7 8 4 11 9
No
В первом тесте из условия на каждом из серверов 1, 2 и 6 будет использовано по $$$8 / 3 = 2.(6)$$$ единиц ресурса, а на каждом из серверов 5 и 4 — по $$$16 / 2 = 8$$$ единиц ресурса.
Во втором тесте из условия на первом сервере будет использовано $$$20$$$ единиц ресурса, а на оставшихся серверах — по $$$32 / 3 = 10.(6)$$$ единиц ресурса.
Название |
---|