CF925B Resource Distribution

题目描述

某软件公司的一个部门有 $n$ 台规格各异的服务器。服务器编号为 $1$ 到 $n$ 的连续整数。假设第 $j$ 台服务器的规格可以用一个整数 $c_j$(人工资源单元数)来表示。 为了保证生产工作,需要部署两个服务 $S_1$ 和 $S_2$,用这些服务器来处理到来的请求。服务 $S_i$ 处理请求需要 $x_i$ 个资源单元。 由于公司技术先进,每个服务不仅可以部署在一台服务器上,还可以同时部署在多台服务器上。如果服务 $S_i$ 部署在 $k_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$ 个整数,表示用于第二个服务的服务器编号。 最后两行输出的服务器编号不能重复。如果有多种方案,输出任意一种均可。

说明/提示

在第一个样例中,服务器 1、2 和 6 各自分担 $8 / 3 = 2.(6)$ 个资源单元,服务器 5 和 4 各自分担 $16 / 2 = 8$ 个资源单元。 在第二个样例中,服务器 1 分担 $20$ 个资源单元,其余服务器各自分担 $32 / 3 = 10.(6)$ 个资源单元。 由 ChatGPT 4.1 翻译