#P16349. [2026年山东第二轮集训]构造题

    ID: 15560 传统题 3000ms 1024MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>数学算法基础二分数据结构可持久化线段树模拟CF2400枚举

[2026年山东第二轮集训]构造题

题目描述

给定一个包含 nn 个整数的数组 aa。每次操作中,你可以选择一个位置 ii(1≤i≤n1 \leq i \leq n),将 aia_i 减少 kk,同时将所有其他元素 aja_j(1≤j≤n1 \leq j \leq n 且 i≠ji \neq j)增加 tt。

求将数组中所有元素变为非正数(即小于或等于零)所需的最少操作次数。如果无法实现,则报告该情况。

输入格式

第一行包含三个整数 nn、kk、tt(1≤n≤1061 \leq n \leq 10^6,0≤k,t≤1090 \leq k, t \leq 10^9)——数组长度及操作参数。

第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n(−1018≤ai≤109-10^{18} \leq a_i \leq 10^9)——数组元素的初始值。

输出格式

输出一个整数 cc——将数组所有元素变为非正数所需的最少操作次数。如果无法实现,输出 −1-1。

如果可以实现,还需输出 nn 个整数 cnticnt_i(1≤i≤n1 \leq i \leq n),表示对第 ii 个元素执行的操作次数。注意必须满足 ∑i=1ncnti=c\sum\limits_{i=1}^n cnt_i = c。

样例 1 输入

4 10 1
2 5 9 -4

样例 1 输出

4
1 1 2 0

样例 2 输入

5 1 100
-1000 -1000 10 -1000 -1000

样例 2 输出

10
0 0 10 0 0

样例 3 输入

2 1 1
1 0

样例 3 输出

-1

数据范围

对于所有数据,1≤n≤1061 \leq n \leq 10^6,0≤k,t≤1090 \leq k, t \leq 10^9,−1018≤ai≤109-10^{18} \leq a_i \leq 10^9。

  • 子任务 1(55 分)t=0t = 0;
  • 子任务 2(55 分)1≤n≤3001 \leq n \leq 300,∣ai∣≤300|a_i| \leq 300,0≤t≤1060 \leq t \leq 10^6;
  • 子任务 3(1010 分)1≤n≤30001 \leq n \leq 3000,∣ai∣≤3000|a_i| \leq 3000,0≤t≤1060 \leq t \leq 10^6;
  • 子任务 4(1010 分)1≤n≤1031 \leq n \leq 10^3,ai≥1a_i \ge 1,0≤t≤1060 \leq t \leq 10^6;
  • 子任务 5(55 分)1≤n≤1041 \leq n \leq 10^4,ai≥1a_i \ge 1;
  • 子任务 6(1010 分)1≤n≤1051 \leq n \leq 10^5,ai≥1a_i \ge 1;
  • 子任务 7(1010 分)ai≥1a_i \ge 1;
  • 子任务 8(1010 分)1≤n≤1031 \leq n \leq 10^3,0≤t≤1060 \leq t \leq 10^6;
  • 子任务 9(55 分)1≤n≤1041 \leq n \leq 10^4;
  • 子任务 10(1515 分)1≤n≤1051 \leq n \leq 10^5;
  • 子任务 11(1515 分)无额外限制。