#L3973. 「JOISC 2023 Day3」曲奇

    ID: 4510 传统题 1000ms 1024MiB 尝试: 7 已通过: 1 难度: 8 上传者: 标签>动态规划背包贪心其他构造思维数学排序难度提高+/省选-

「JOISC 2023 Day3」曲奇

题目描述
题目译自 JOISC 2023 Day3 T2「クッキー / Cookies」

理惠女士喜欢做曲奇。她做了 NN 种曲奇,第 ii (1iN)(1\le i\le N) 种做了 AiA_i 个。为了卖这些曲奇,她会将曲奇打包进盒子中。然而,需要满足以下条件:

  1. 对于每个盒子,在其中的曲奇种类应该是不同的
  2. 对于每个盒子,在其中的曲奇数应该等于如下 MM 个数中的一个:B1,B2,,BMB_1,B_2,\ldots,B_M

给定理惠女士做的曲奇的信息和打包的要求,写一个程序确定是否可以把所有曲奇打包。此外,如果可以将所有曲奇打包,你的程序应该输出一种使用最少的盒子的打包方案。


输入格式
第一行一个整数 NN

第二行 NN 个整数 A1,A2,,ANA_1,A_2,\ldots,A_N

第三行一个整数 MM

第四行 MM 个整数 B1,B2,,BMB_1,B_2,\ldots,B_M


输出格式
如果可以将所有曲奇打包并满足条件,第一行输出最少的盒子使用数 xx。接下来输出 xx 行表示打包方案。第 kk (1kx)(1\le k\le x) 行先输出一个整数 ckc_k,表示第 kk 个盒子中的曲奇数,接下来在这行输出 ckc_k 个整数 vk,1,vk,2,,vk,ckv_{k,1},v_{k,2},\ldots,v_{k,c_k},表示放在这个盒子中的曲奇种类。如果在满足使用盒子数最少的情况下,有多种打包方案满足条件,输出任意一种均可。

如果不可能将所有曲奇打包,输出一行一个整数 1-1 即可。


样例 1
输入:

7
1 1 1 1 1 1 1
3
1 2 3

输出:

3
2 1 7
2 2 6
3 3 4 5

在这组样例中,可以按如下方式将 77 块曲奇打包进 33 个盒子中,并满足条件:

  • 将第 1,71,7 种曲奇放进第一个盒子中,每种曲奇放一个
  • 将第 2,62,6 种曲奇放进第二个盒子中,每种曲奇放一个
  • 将第 3,4,53,4,5 种曲奇放进第三个盒子中,每种曲奇放一个

如果你的程序按如上方式输出将被判为正确,因为不可能将这 77 块曲奇放进 22 个或更少的盒子中并满足条件。如果有其他打包曲奇的正确方式也会被判为正确。

这组样例满足子任务 1,3,4,5,61,3,4,5,6 的限制。


样例 2
输入:

5
5 3 1 2 4
1
4

输出:

-1

在这组样例中,不可能将 1515 块曲奇打包进盒子中并满足条件。因此输出 1-1

这组样例满足子任务 2,3,4,5,62,3,4,5,6 的限制。


样例 3
输入:

7
5 4 4 2 1 1 1
2
2 6

输出:

7
6 1 2 3 4 5 6
2 2 1
2 3 1
2 4 1
2 7 1
2 3 2
2 3 2

这组样例满足子任务 4,5,64,5,6 的限制。


数据范围与提示
对于所有输入数据,满足:

  • 1N15,0001\le N\le 15,000
  • Ai1A_i\ge 1A1+A2++AN15,000A_1+A_2+\ldots+A_N\le 15,000
  • 1MN1\le M\le N
  • 1BjN1\le B_j\le NBj<Bj+1B_j<B_{j+1}

详细子任务附加限制及分值如下表所示。

子任务编号 附加限制 分值
1 N500N\le 500Ai=1A_i=1 6
2 N500N\le 500M=1M=1 7
3 A1+A2++AN15A_1+A_2+\ldots+A_N\le 15 12
4 A1+A2++AN500A_1+A_2+\ldots+A_N\le 500 45
5 A1+A2++AN3,000A_1+A_2+\ldots+A_N\le 3,000 15
6 无附加限制